I've never had screen tearing problems. I always run in a window (usually at 2x), max out the frame skip, and often have turbo on (I usually play rpg/strat type games, and want to get through the long text parts and monotonous walking around parts as quickly as possible. I usually turn off the speedup on shooters).
Stretching might be part of your problem, specially in regards to the gameboy games. Keep in mind that the GBC screen is considerably smaller than the GBA screen, and thus has to be stretched more in order to fit the computer screen. This would explain why GBC runs slower.
EDIT: This would also explain why it speeds up when you turn on the toolbar. Having the toolbar on reduces the ammount that the screen can/must stretch to fit your monitor.
The above priority might also be part of it. Sometimes raising the priority level improves performance, but sometimes it hinfders it instead. Experiment with different settings and see what works for you.
As far as "missing that 1fps", you'll never notice it at all. I nearly always run at a frameskip of 9fps, and only rarely do I notice any problems. Running at a frameskip of 1fps wouldn't be a problem at all.