EDIT: (looks like I typed a lot, pretty much my review of apps the last two days, no time to proof at 3am)
I was new to all this a few days ago too
Here's a forum I came across to find hot themes.
http://macthemes.net/forum/viewforum.php?id=24 I'm personally using Suave. I like the smooth look, slightly smaller icons. The grayish background really lets the color of the icons pop without being harsh. The tiny icons will work well if you want a 5 icon dock, or 5 rows and columns.
Glasklart is an interesting one. Pretty much transparent icons with a white silhouette shape for the artwork. The main goal is to make the backgrounds the star, showing through the icons. With BossPaper, you can set up your own slideshows or single image. Just make sure the Winterboard theme is doing it's own slideshow too (many warnings in BossPaper)
You got Lockinfo. I'm actually using it as a home screen, since I didn't want all my personal info on the lock screen, but it's nice you can customize it so much. And finally, a history for notifications on the iPhone
Then the major well know apps.
SBSettings: What I wished I had since getting the iPhone, a quick way to turn off bluetooth, adjust brightness, etc, and the tip of your finger. Basically offers toggle switches for these functions, and more. Like supposedly if you get the 3GUnrestrictor, a toggle can be added to SBSettings to turn that on and off as needed. Also offers a quick respring, incase any app glitches.
3G Unrestrictor: Just installed this today for $2.99. I added youtube to its list, and bang, high quality videos on 3G with no lag. I'll also see it usefull for downloading apps that are too large, especially when an app goes on sale and you can't get to a computer or wifi to purchase it before the sale is over)
Backgrounder, I'm sure you've heard of this.
Music Controls: A $5 app, but limited free use with Pandora, and 5 day full trial. It seems to be able to multitask music apps without the aid of background. Basically, from what I tested with Pandora, it makes using it as seamless as the iPod works. Just close it normally, it still plays, double click home, you get the pop-up to skip and pause, open Pandora, or your app switcher. Even works on the lock screen. Even cooler is it fixes stereo bluetooth controls. I use a bluetooth handsfree device to listen to music in my car, but it's frustrating due to Apple not include skip tracks coding, only play and pause. This fixes that, and it works for Pandora.
Infinidock: A $1, but works amazing. Lets you simple drag icons to the dock, as many as you want, and you scroll horizontally through them. Tell it to show 4 icons at once, 5, 10, etc. To have it auto snap in pages of the amount you chose, or snap on an icon (so none are left half show). Works nice.
Kirkae: With backgrounder, you may want an app to manage open apps, but this does more than just flipping between open apps. Normally, say in Backgrounder, you decide to go to another app, you hold the home button, it enables backgrounding. Instead, with Kirkae, double click home (or other options). It will pop up a simple interface showing everything that's running, with the current app listed as foreground. A great time saving feature is if you select another app, it automatically uses backgrounder on the current app. What if the app you want to switch to isn't running you say? You can have a custom favorites tab. Or something obscure, also can have a spotlight search tab and reveal springboard, all without exiting the current app. I find this handy because I often forget if I already enabled backgrounding once, and doing the normal backgrounder exit by holding the home button, I often disable it by accident.
Lockdown. Free app that lets you password protect your apps, even if it's running, if you use the springboard, it will ask it. Though, again, if the app is running, using a switching app like Kirkae probably gets around that. A nice feature is lock all, unlock all, or disable the whole thing. So say you lock on your personal apps, but don't want to keep typing a password. Well, you can disable the whole program with a switch while you use it, but can turn it back on when you might have to let another use your phone for a while.
Categories: free folder app, but also get the $1 add-on, CategoriesSB, which makes it fast and more iPhone like, simply a must if you use it. In options, turning of background and title image lets your background show through.