I hear you there. I was a 2D games graphic programmer in the early 90's when a screen was 640x480 and 1byte per pixel and PCs were SLOW... The first thing to look at is if you can optimise your "fairly large amount of code" for every pixel. That's a good area to convert to assembler, and/or recode the branching based on the most common options first to reduce time per pixel. Some graphics tricks we used back in the dark ages might help, like;...
My current screen is 176 x 132 pixels and has 16 bit of color depth per pixel. As you may all know, somewhere in my code I have a for loop nested in another in order to go through all the pixles. And in every itteration I execute a fairly large amount of code. Therefore this is the reason that the PIC18F4685's 10 MIPS is sort of slow.
...