Since there are so many Cydia apps around, I thought I'd pick out some of the more notable, useful apps that I have came across or am using right now. If you think I have missed out any Cydia apps that should be included in this list, please let me know and I will duly update it.
For obvious reasons, I have not included the one most notorious app so please do not reply to me asking me to include it. If you do, I will report that post to the mod. I will also not include iSt**my since there might be underage forumers. 
Hope you guys understand my position. It's better for me to report than the mods to close this thread. I took several hours to compile this list for your benefit so please, help me to help you. 
You may think it is crazy to pay for apps but for those who does coding, you will appreciate all the hard work involved. It's not a 9am-5pm routine task. It's worst when you have got responsibilities to paying customers. 
Also for those who doesn't know this, yes you can share your account on multiple iDevices. I am sharing my Cydia account with 4 iPhones, 2 iPads and one iPod Touch. So in that sense, it is money well spent since I only need to fork out once. And don't worry, it's is perfectly accepted. 
So without further ado, I present the list of apps which I think/been suggested worth considering to get:
Action Menu: Free
Author - Ryan Petrich
Description - Adds action to the Action Menu
Activator: Free
Author - Ryan Petrich
Description - Activate apps via gestures, buttons and shortcuts
afc2add: Free
Author - NetMage
Description - Package to add afc2 service for USB browsing of filesystem. Adds the afc2 service and reboots the phone, to fix issues for folks unable to use USB browsers (like iPhoneBrowser) with blackra1n.
AppBackup: Free
Author - Scott Wallace
Description - An iPhoneOS application that backs up and restores the saved data and preferences of App Store apps. To back up all apps at once, tap All at the top-left of the screen, and select Backup. To restore all apps that have been backed up at once, tap All and select Restore. (You must have at least one app backed up in order to see this option.)
AttachmentSaver: USD $3.00
Author - Youssef Francis
Description - Mail.app as it was meant to be. This package adds an extension which allows you to save Mail attachments directly to your iPhone. It unlocks the ability to download *all* attachments of all types, whether supported by Mail or not, and then save them into a folder on disk.
Auto3G: USD $5.99
Author - Kay Cee Press, LLC
Description - Auto3G extends your battery life by automatically turning off the 3G radio (leaving on the 2G radio) when you lock your iPhone and automatically turning on the 3G radio when you unlock your iPhone. You can also have Auto3G automatically turn off the 3G radio when you have a Wifi connection. You can even have Auto3G keep your iPhone on 2G at all times unless specific applications you designate are running. This way you always have the speed of 3G when you need it without the battery loss.
AutoSilent: USD $2.99
Author - iPhonePackers
Description - Bypass silent switch. Puts in silent mode automatically during meeting, nights and as configured by user. Syncs with calendar and goes silent during meetings.
Backgrounder: Free
Author - Lance Fetters (ashikase)
Description - Run iPhone Applications in the background!
Backgrounder is a Mobile Substrate-based extension to Apple's SpringBoard application launcher that allows applications to run in the background (applications are normally terminated upon suspension).
BackLiter: USD$ 0.99
Author - Enscand, Inc
Description - A new one-touch utility app for controlling your phone's backlight levels.
BiteSMS: Free with ads/SGD $11.95
Author - biteSMS
Description - You love your iPhone as much as we do? You text all the time? Want more features? Then biteSMS is for you, with lots of extra features like Smileys, Quick Reply, Quick Compose / Quick Call, Privacy, a Character / SMS Counter and much more!
Note: Not sharable among multiple iDevices
CalendarPro4: Read note below
Author - phoenix3200
Description - Customize when and how your phone will ring based off of your Calendar appointments! CalendarPro4 seamlessly integrates into Calendar to provide you with the option to set a ring profile for a particular event, create new ring profiles, or set up rules to apply styles for matching events or times. If you're in school or in business, this app is for you!
Note - This is a paid upgrade of the original app called CalendarPro(USD $3.99) which meant for iOS 3.X only. The upgrade will cost another USD $2.49 which makes it compatible on iOS 4.
Categories: Free
Author - BigBoss
Description - Move your springboard icons into folders!
CategoriesSB: USD $0.99
Author - Lance Fetters (ashikase)
Description - Integrate Categories into Springboard
CyDelete: Free
Author - Dustin Howett
Description - Delete Cydia packages from SpringBoard, just like App Store applications!
Cylay: USD $19.99 Annual Subscription
Author - iFonetec Support
Description - As the first anti-theft and security iPhone software in the world, Cylay has been used by over hundreds of thousands users and helped hundreds of users to find their lost iPhones.
Cyntact: USD $1.00
Author - Jay Freeman (saurik)
Description - show profile pictures in contact lists
Firewall iP: USD $2.99
Author - Yllier
Description - Firewall iP is the only security tool of its kind for iPhone and iPod touch. Firewall iP allows you to block outgoing connections (TCP & UDP). It hooks into applications and will warn you if the app wants to establish a connection to a host and shows you the hostname. Then you have the options to allow or deny the connection once/always or allow/deny all connections for the application. Port specific blocking is possible.
FolderEnhancer: USD $1.99
Author - Lance Fetters (ashikase)
Description - Improves and extends iOS4 folders.
Note - Not compatible with Infinifolders
FoldersInFolders: USD $1.99
Author - Elias Limneos
Description - Add Folders inside Folders!
Note - Not compatible with Gridlock
Gridlock: USD $0.99
Author - chpwn
Description - A powerful tweak that allows you to arrange your icons however you would like, with drag and drop simplicty. No longer will you need blank icons which have ugly shadows, or you have to remember not to tap.
Note - Not compatible with FoldersInFolders
iBlueNova: USD $5.99
Author - MeDevil
Description - iBlueNova, the world first application that enables the file transfer via Bluetooth on your iPhone! Take a look at MORE INFO before installing.
Iconoclasm: USD $3.00
Author - Yanik Magnan
Description - easily customizable icon layout framework
iFile: USD $4.00
Author - Carsten Heinelt
Description - A File Manager and Viewer. iFile is a file manager runnning under user root. Works for iPhone, iPod touch and now Ipad. It allows fast navigation through the iPhone file system. You can directly view files of various types, e.g. movies, sound, text, HTML, Microsoft types, PDF, various compressed formats. For PDF files direct jumping to pages is possible. ZIP packing and compressed file unpacking is also supported. Files can be sent as email attachments. Text files and property lists can be edited. Folders and files can be bookmarked. In addition, files can be uploaded and downloaded from iFile's built-in web server.
Infiniboard: USD $1.99
Author - chpwn
Description - Vertically scroll your home screen pages! Infiniboard lets you add as many icons as you want to each page, and access them through a flick up and down. Many settings provide full customization - and resprings don't mess up your icons.
Infinidock: USD $0.99
Author - chpwn
Description - Infinidock is the ultimate dock scrolling and customization tool! ;Add as many icons as you want to your dock and scroll back and forth; Set how many icons per page; Give your dock pages!
Infinifolders: USD $1.99
Author - chpwn
Description - Scroll your folders with unlimited icons! Infinifolders lets you add as many icons as you want to each folder, breaking the 12-app limit, and access them through a flick up and down. Many settings provide full customization (no respring required!) - and resprings don't mess up your icons.
Note - Not compatible with FolderEnhancer
IntelliDial: USD $2.99
Author - Intelliborn
Description - Get easy access to dial your favorite contacts from your lock screen. IntelliDial can be configured to display in convenient Tiles or more entertaining in Cover Flow format!
Inspell/SBsettings: USD $3.99
Author - Ryan Petrich
Description - Inline spelling corrector for iOS. Uses Hunspell dictionaries to support a variety of different languages. Also, Inspell can setup shortcuts to expand frequently entered text.
iRealSMS: EUR $9.99
Author - SpiritOfLogic
Description - Do you love your iPhone but hate the limited Messages app? Frustrated with missing basic functions that are available on most other cell phones? iRealSMS 3.0 fills the gap with Folders, Drafts, etc., and then comes with features such as QuickReply, QuickSend, Contact Pics, Smileys, Templates, Search Feature, Forward via Mail, Privacy Settings, Password Lock, Character Counter & much more! Use it as a FULL Messages app replacement or just take advantage of the QuickReply & QuickSend.
Note: Not used personally by me
iRemix: USD $2.99
Author - Efiko Software
Description - Enhance your iPod experience.
iSmart Dialer: USD $3.99
Author - iSmartDialer
Description - iSmart Dialer adds layers of functionalities to your "Phone" Application. Including: Searching for contacts using the Keypad, Speed Dial, Auto-Complete, SMS / E-mail from inside the dialer and much more.
Note: Not sharable among multiple iDevices
iWipe: USD $2.99
Author - Jay Freeman (saurik)
Description - Want to make sure a deleted confidential email or embarrassing photo is purged forever from your iPhone? Simply deleting a file doesn't guarantee it's gone for good, and doing a restore only quick-formats the iPhone. Protect your deleted data from being recovered by hacking tools and prying eyes, or in the event your iPhone is stolen.
iWipe is a simple utility for zeroing out the free space on your iPhone. The tool does not delete any live files, but uses the same method that Mac OS X uses to zero free space: it creates a large temporary file, which writes zeroes over the free space where deleted files can still reside. The entire iPhone user partition is cleansed, forever purging deleted photos, email, voicemail, and other deleted files.
This helpful utility can be run periodically to effortlessly clear out old data and ensure it is beyond recovery. Because it doesn't erase your content or settings, you won't need to recover any backups or risk losing data. Actual erase time varies depending on the amount of free space on the device. You're still able to lock or receive phone calls while iWipe is running.
LiveClock: Free
Author - Joshua Lee Tucker
Description - Animated Clock icon on the SpringBoard. Adds customizable animation to the SpringBoard Clock icon. Includes a few extra themes for use with WinterBoard (if it's installed). Does not work on some older models
LockInfo: USD $4.99
Author - David Ashman (Stimpy5050)
Description - Customize your lockscreen with calendar, mail, SMS and other device information.
MakeItMine: Free
Author - Erica Sadun
Description - Change your carrier name to whatever you'd like.
Mobile Profile: USD $3.99
Author - Aaron Wright
Description - Create custom profiles with iPhone system settings that you define for each individual profile you may create! You can also add a description to your profile for a quick reference as well as rename the profile. You can also quickly enable or disable iPhone services such as Wi-Fi and Bluetooth with Quick Profiles.
MultiCleaner: USD $0.99
Author - da_petcu21
Description - Because iOS 4 multitasking sucks.. Tired of having to return to SpringBoard, double-tap the home button, tap&hold, then press the small quit button to quit an app? Tired of removing closed apps manually from the multitask bar? With MultiCleaner you can quit apps with just an Activator shortcut and customize the multitask bar however you like. You can even reorder apps in the bar.
Multifl0w: USD $4.99
Author - Aaron Ash
Description - Exposé-like multitasking interface
MultiIconMover: Free
Author - Lance Fetters (ashikase)
Description - Move multiple SpringBoard icons at a time.
My3G: USD $3.99
Author - Intelliborn
Description - Now iOS4 compatible with FACETIME! My3G: Take back your 3G! My3G makes Apps believe that they are on WiFi instead of 3G. With My3G, you can now watch HiDef YouTube videos, use Skype/Fring/Other VOIP apps over the 3G network!
Note - Not compatible with 3G Unrestrictor
MyProfile: USD $6.99
Author - Intelliborn
Description - Profile your iPhone! Adjust how your iPhone behaves based on time, location, and more. Handles Custom and Repeating Alerts for Email, SMS, Phones based on sender/subject/mailbox, and more!
MyWi 4.0: USD $19.90
Author - Intelliborn
Description - All New Tethering on iPhones + iPad for iOS 4.0! Includes support for 3.1+ and all iPhones (including 2G/3G/3GS) and iPad! Create a WiFi HotSpot with a press of a finger! Wherever you are - you can connect your laptop or other mobile device to your iPhone easily! You can also use MyWi 4.0 to enable USB Tethering on 3.1!
NoLockScreen: Free
Author - Tom Zickel
Description - Disables the "Slide to unlock" part of the lock screen, so if you don't have a passcode or pending message, it will skip the lock screen completly when unlocking. On 4.X/3.2+ it instantly goes back to what you were doing. On 3.1 and below it will show the lock screen for a split second + does animations.
PDF Patch (CVE-2010-1797): Free
Author - Jay Freeman (saurik)
Description - protects against known PDF exploit
PhotoShare Web: USD $0.99
Author - Youssef Francis
Description - PhotoShare Web allows you to upload your Camera Roll photos, and other items in your Photo Libraries, directly to web services such as ImageShack, Flickr, and Twitpic. Its integration with the built-in Photos and Camera application allows for a seamless photo experience, rivaled by none.
PkgBackup: USD $4.99
Author - Jibril Gueye
Description - This is a K.I.S.S.(Keep It Simple, Stupid) backpup application that allows you to back up & restore all the cydia packages installed in your iphone. You can even share/exchange/send your packages lists to others. I'm counting on your support & comments to make this app more KISSable
. The application is also Facebook Connect enable so that you can proudly share the apps you have on your iPhone. Best of all, with SBOrganizer, it *NOW* backups & restores your springboard layout.
QuickScroll 2: Free
Author - KennyTM~
Description - Quickly scroll through anything. PDF paging. Initiate with two-finger or triple tap.
Recent/CallLog Delete: USD $1.49
Author - MirrorDev
Description - Enabled MobilePhone Recents Delete Extension. Delete individual calls from Recent Calls list.No need install more apps.Just delete from the phone application.
Remove Background/SBsettings: Free
Author - rono23
Description - Remove all apps from the task switcher / And the apps processes killed too.
Remove Recents: Free
Author - BigBoss
Description - Removes Recents from the task switcher in 4.0. The stock task switcher is really annoying. Everytime you launch an app, it sits in the task switcher even when it is not running. Apple considers this a feature I guess. It's really lame. Pretty soon you have a ton of apps down there with no idea what's running or not (most of it is not). This extension will remove all the recents so that only running tasks show up, the way it should be.
Rotation Inhibitor: Free
Author - Ryan Petrich
Description - Allows enabling/disabling interface rotation from SBSettings
When Rotation is disabled Safari, iPod and other applications that change their orientations with the device will no longer do so.
Safari Download Manager: USD $5.00
Author - Dustin Howett
Description - Safari Download Manager is an extension that adds a powerful, highly-configurable download manager to the iPhone's web browser. Like never before, you can take control over downloaded file types, and harness the true power of the network connection on your device.
Note - Safari Download Manager is just that, a download manager. It will, by itself, not allow you to view your downloaded files; for that we recommend installing iFile. Purchasing Safari Download Manager will save you USD $2.00 on iFile.
SBOrganizer: USD $0.99
Author - Jibril GUEYE
Description - The purpose of SBOrganizer is to provide a portable way to reorder your springboard application icons. Portable because SBOrganizer allows you to order your springboard application icons as you want *right from your device*. You no longer need to have or be connected iTunes to reorganize your springboard application icons. Furthermore, you can create *unlimited* pages and *merge* them. Not to forget, you can brag about your application use using Facebook Connect. To do so, you'll need to click 'Connect with Facebook' before you start ordering your springboard.
Just like PkgBackup, this application is K.I.S.S. (Keep It Simple, Stupid). Just click on 'ReOrder', do your magical reordering and click on 'Done'. Voila!
Starting with v3.1.0, PkgBackup will save your SBLayout, too.
SBSchedule:USD $3.99
Author - Tom Zickel
Description - Create profile groups of various settings, manage your device brightness, volume, ringtone, phone, 3G, location, ssh, bluetooth and much more...
Setup your profile groups to launch at specific times or quickly via a shortcut from any app
SBSettings: Free
Author - BigBoss
Description - Welcome to convenience! Move your important toggles directly into Springboard where they are always available instantly even while other apps are running.
Note - This does not come with an icon. You can swipe the statusbar to bring down the main window. You can configure in activator settings other methods of opening the SBSettings window. Customize it to your liking!
ScreenDimmer: USD $1.99
Author - KStreich Dev, Yllier
Description - ScreenDimmer allows you to save battery life by automatically dimming your device's screen after a pre-defined time; or if you wish by turning the backlight off.
ShakeToUndo Killer: Free
Author - Yllier
Description - Annoyed of the "shake to undo"-function in iOS? Here is the solution: This little tweak lets you disable "shake to undo". It comes with a SBSettings-Toggle; you can toggle within apps without having to restart it.
Silent Photo: Free
Author - hrutkaymods
Description - This removes the annoying camera shutter noise when taking a picture.
SwitcherPlus: Free
Author - switcherplus
Description - SwitcherPlus allows the native multi-tasking "Switcher" feature to also be used in the Lock Screen Mode.
User Agent Faker/SBsettings: Free
Author - Conrad Kramer
Description - An easy to use User Agent Faker that works in every single app. Change the configuration from Settings app
Wi-Fi Sync: USD $9.99
Author - Greg Hughes
Description - Wi-Fi Sync enables wireless syncing with iTunes at the touch of a button. Never go looking for that USB cable again. Sync from the car, bed or shed whenever it suits you.
WiCarrier: Free
Author - Ryan Petrich
Description - Replaces status bar's carrier name field with the currently connected WiFi network
Winterboard: Free
Author - Jay Freeman (saurik)
Description - Give your iPhone or iPod Touch a graphical overhaul! WinterBoard provides hooks that let graphics artists safely and simply theme almost anything in Apple's OS, including third party software downloaded from App Store. Multiple theme packages can be installed at once using the configuration interface: simply drag themes into a priority order.
3G Unrestrictor: USD $3.99
Author - Kim Streich
Description - 3G Unrestrictor allows you to go around the iPhone's limitations and restrictions of not being able to use some applications like FaceTime, Skype or SlingPlayer while on a mobile internet connection like 3G or EDGE as well as many other things.