A flux pen will change everything.
I like the Kester 2331-ZX. You could use radio shack flux paste, but honestly the pen works much better with less mess. I've tried the no clean Kester but I don't like it as well. Anyway your jaw will drop the first time you see solder flow after application of flux.
I proved to myself that it's possible to solder with a $ Store cheapo crap soldering iron provided I used a flux pen. (Bot Thoughts: Dirt Cheap Soldering Iron)
The next great thing is a brass sponge tip cleaner.
Works so much better than water sponge, with so much less mess and no need to pour on new water.