As far as just free ones go, I have Mocha VNC Lite that I use to connect into my computer at work. I use Palringo Instant Messenger (you can use AIM, Yahoo, MSN, etc.), and installed White Noise for background noise when I'm traveling.
I really like Pandora and AOL Radio. Pandora lets you pick an artist that you like and it will find other artists that are similar and play their music. AOL Radio lets you listen to radio stations around the country.
I just got a touch a few weeks ago as well. So far my favorite games are Aurora Feint and Solitaire City Lite. Aurora is a tetris-type game with a story and Solitaire City is a slightly souped-up solitaire game (obviously).
I haven't done anything other than free games yet, but I really want a good racing game.
Oh and I just downloaded Remote, which is a very cool idea.....but I haven't set it up yet.
Shazam is amazing, but doesn't work on the touch, only the iPhone.....but I guess the touch does have mic compatibility, so you could plug in a mic and use it I suppose......VERY cool app though.
Urbanspoon is great and has Des Moines as one of the cities. NowPlaying is good. Facebook is good. APMobile News is one of my favs as well. All of these are free too.
I'll echo Pandora Radio and Remote as great apps. When you're on WiFi for sports scores and stuff I'd go with Sportacular and Plusmo College Football Live (both free). Sportacular will let you enter your fantasy players to get customized stats too which is cool. Some good games: Tap Tap Revenge (a bit like DDR and Guitar Hero - free), Enigmo (puzzle game), MotionX Poker (dice poker - strangely addictive), Solebon (30 solitaire games - has a free version to try), SuperBall 2 (brick breaker game with over 300 levels - also has a free version). A lot of the other non-game apps I like make use of GPS location services so that's not very helpful for your Touch.
The iTunes Top 100 Free and Top 100 Paid lists are good for a starting point. The reviews on iTunes are increasingly helpful now that they're only allowing people to rate what they've actually bought or downloaded free.
I also scan this page often for ideas because there's so many apps being added each day: