Don't get me wrong- the App Store is incredible and unmatched. There truly is an app for just about everything on the iPhone. Well, everything that Apple approves of anyway. Fortunately, for those special apps that just can't pass Apple Legal muster, there is Cydia- the third party App Store alternative created by hacker Jay Freeman (aka saurik). Cydia is only available by jailbreaking your iPhone, a process that while relatively simple may not be for faint of heart. Here are some of the best apps you'll never see on the App Store.
Winterboard A glaring, though likely intentional omission from the iPhone's 'Settings' app is the ability to alter the appearance of the UI in any significant way. Thankfully, Winterboard (a pun of iPhone's UI manager 'Springboard'), is an app that allows you to install themes which you can either create yourself or download from Cydia. At this point, there are hundreds of themes and appearance mods at the disposal of jailbreakers.
SBSettings SBSettings is a candidate for my most oft-used jailbreak app. It is a simple add-on that lets you swipe across the status bar (either in the home screen or while an app that doesn't hide the status bar is running) to bring up quick, customizable settings and/or toggles. As I am borderline OCD with device battery conservation I like to have brightness control as well as Wi-Fi and 3G toggles in mine. SBSettings is fully skinnable so you can match the appearance of your Winterboard theme.
Netatalk When you jailbreak your phone, you are able to access the root file system any number of ways, including ssh (via OpenSSH) or a simulated terminal (MobileTerminal) on the device itself. Netatalk, however, is a much more Mac-like option, enabling you to browse the iPhone file system over AppleTalk. Simply install Netatalk, enable File Sharing on your Mac and voila! The device will appear under 'Devices' in a Finder window and you can navigate through your iPhone's files without any prior UNIX knowledge.
Cycorder For those of us relegated to non-3GS iPhones, Cycorder is a video recording app that performs surprisingly well, considering that the 2G and 3G camera hardware was supposedly not designed for video. Makes you wonder if Apple intentionally locked this feature to bolster 3GS sales.
iBlacklistIf you're tired of getting repeated calls from persistent telemarketers or you just don't feel like talking to that certain special someone, iBlacklist allows you to automatically block calls, either sending callers on your blacklist to voicemail, giving them a busy signal, or just ending the call. You can also set up whitelists to only allow specified numbers to reach you or set up different behaviors for different days of the week. The amount of customization is actually quite impressive; it's clear a great deal of work went into creating iBlacklist before it was quietly blacklisted by Apple.
PDANet While AT&T continues to delay the rollout of tethering (not to mention MMS!) and various rumors have been flying around regarding the cost of the service, us jailbreakers have been happily tethering for months. PDANet is easy to use and free to download. Just set up an ad-hoc network on your laptop, connect to it via your iPhone's Wi-Fi settings, start up PDANet and you'll be clipping along on your laptop at vaguely tolerable 3G speeds.
Five Icon DockNot an app, per se, Five Icon Dock is a hack which can be obtained and installed through Cydia that does exactly what it sounds like: fits even more stuff right down there. Before Five Icon Dock, I was constantly faced with the dilemma of whether I needed Safari or Maps at my most immediate disposal, but now I can have my cake and eat it too!
Swaptunes This little app lets you sync your music to two different iTunes libraries. Obviously this feature was omitted and this app denied from the App Store as an attempt to battle piracy, but there are also perfectly legitimate reasons to have two different machines with two different music libraries- home computer, work computer perhaps?
MXTube Finally, a way to watch YouTube videos offline! MXTube allows you to download YouTube videos to your mobile device for viewing on the subway, plane, or in those pesky dead zones. Functionally, it works similarly to downloading podcasts from the iTunes store, and even allows background downloading.