The problem is this: my monitor can't display lower than 800 by 600 for some reason, most other programs it's just a case of changing the .ini, but I can't figure out how to do it with Gens. If anyone knows, please let me know.
What OS and video card are you using? I don't think you can change it in Gens, if you look at the manual it only mentions full screen at 640x480, and nowhere in the program/help files/config do I see where you can change that.
When I first installed XP, I couldn't go lower than 800x600 with my GeForce II MX.
I installed Multires, which is a handy little on-the-fly resolution switcher, that if I remember correctly, automatically enabled 640x480 switching on install.
If that doesn't work, it's probably more a matter of finding a site that show how to key custom resolutions into the registry (be careful). There well may be a custom tool for your card that would make the process easier that can be found on those trendy high-end 3D card tweaking sites...
Try checking on your video card manufacturer's site if nothing else.
Similar to that, the situation is Windows XP with a Geforce MX440. Under it's properties, it lists 640by480 as a valid mode which is what lead me to believe it was the monitor not the card. Switching to 640 with multires gives the same distorted, boxed in result.