if you go to google image search, you can drag images into the search bar to search based off the image itself instead of keywords. this is useful for finding the original versions of images, which are often higher res than secondhand versions that you just find through regular google searching. tineye is another search engine that I use for this purpose.
waifu2x does complex stuff to upscale your image in a way that doesn't look as bad as simple interpolation based upscaling. I didn't know about this when I was actively fixing bgs for people, but if i had it would've made my life a lot easier.
the online demo doesn't allow images over a certain resolution, so you may need to download the program itself. here are two different versions that you can use: waifu2x-caffe, koroshell if you have a dedicated graphics card, waifu2x-caffe will take advantage of that and be a lot faster than koroshell.
and if you just need a simple image editor, I suggest Paint.NET.
if none of the above helps you, you can message me to see if I can help in some way.
and just in case some people aren't aware, the new max res for bg images is 1920x1200.