http://www.freeappalert.com
That site shows the apps that went free today. If you keep up with it for a few weeks you'll fill your phone with games, utilities, etc. Since there's so much duplication it isn't long before you find an app that you need but don't want to pay for. A lot of these apps are only free for a day so they get a boost in "popular app" lists, and get more reviews.
Due to that, I've only paid for a few apps.
Things I either bought, or would buy if I hadn't gotten them for free:
Air Mouse - control your computer with the iPhone - makes an excellent remote, and works with multiple computers over wifi (and bluetooth, I think)
Ragdoll Blast - awesome fun physics puzzle game
SPL Meter - find out how loud your environment is - useful if you work or walk in really noisy areas, see if hearing damage may occur
SkyVoyager - (or the cheaper less featurefull version) excellent astronomy app. Uses GPS, compass, and accelerometer so you can "aim" it at the sky and it'll show you the star map of what you should be seeing, and identify stars, features, etc of the sky. Just awesome - was free for a day awhile back, but I'd probably pay for it now with all that it does.
Doodle Dots, doodleguess, doodlesearch, doodleships - nice free apps for dots, hangman, word search, and battleship. 2 player or one player for dots and battleship.
Tuner - if you play an instrument, this tuner works pretty well.
Things I got for free, but probably wouldn't pay for if they are no longer free:
App Miner - helps find apps
Pandorabox - find apps
Tweetdeck - decent twitter client
VehiCal - keep track of your gas mileage, car maintenance and repair, etc.
Sport Lite - MotionX GPS app for hiking, waypoints, tracking/backtracking, etc
BetterLists - decent "grocery list" - lets you set up your own lists and fields in the lists so you can make them as complex or simple as needed.
SparkPeople - Diet/health management
Just Light - flashlight
iMapMyRide - cycling/jogging/walking path mapping app - integrated with website. Lots of stats. This is the free version, and it works fine.
Flickr - Useful if you have a flickr account
Flood-it! - simple puzzle
Boxed In - Decent push-the-boxes-around puzzle game
Piratizer - automatic face recognition, adds pirate accessories to picture for the lulz
Skype - free VOIP (when near wifi)
SpaceGeek - Nasa TV streaming - handy when they're doing a launch, landing, or crash stuff into the moon.
IRCHon - Halfway decent (free?) IRC chat if you need one. Works well with halforums IRC.
KatamariLite - Interesting implementation of katamari, free. Full version available for $
SoundMatrix - sequencer - create your own loopy sounds
iRelax - Relaxing sounds. Ocean, river, rain, thunder, chimes, birds, etc - mix and match. I like river, ocean, rain, thunder together, and so, apparently, does my 7 month old baby. They have a premium version that has more, but the free one is more than sufficient for me.
Tap Sudoku - Yet Another Sudoku clone. Decent interface. I also have Tile Sudoku, and haven't played them enough to decide which to keep.
PtPeintuLite - really nice drawing program.
Mixed - word scrambles, good practice for scrabble
Movosity - accelerometer mapping/drawing in 3D - unique app. Want to try on roller coasters but haven't yet.
TED - videos from TED conferences
ToneBoard - Another sequencer, very simple and nice, no advanced features.
-Adam