The characters are models, rendered in realtime, and can be run at the screen's native resolution. The backgrounds are pre-rendered images, though, which means they need to be stretched out to display, which causes pixelation. The only reason you never noticed this in the original is because the playstation runs at such a low resolution that everything looked like this, but it wasn't really noticeable (not to mention, the CRT televisions of the '90s made things a bit blurry, which did a good job at hiding this).
The best solution is to make completely new backgrounds. Team Avalanche is working on that, but it's nowhere near done yet; it takes a long time and a lot of work for each individual screen.
A less good, but much faster solution that's already been done is to upscale the old backgrounds.
Omzy's FFVII Field Pack (which might be included in Bootleg, I don't know for certain) does this, to varying success. It's obviously not as good as completely remade backgrounds, but it might be enough to hold you over until newer backgrounds are made.