Here's an update of the homebrew I've recently added to the DS:
Now that R4 includes auto-DLDi patching, there's now no excuse not to experiment as it's a simple case of drag and drop.
Firstly it's worth checking out
the following wiki list (near the bottom of the page) of compatible 'brew, then away you go.
I personally have
DSdoom. I have the Doom 1 orig wad, but I prefer Doom 2 so I'm working my way through that instead at the mo'. The controls are pretty spot on (touch screen not used though) and it looks and sounds spot on.
I also have
FrodoDS, as mentioned above. At the mo' I have Bruce Lee, Panther, Gauntlet, Starglider, F15 Strike Eagle, Frightmare....amongst others. Still on the search for ACE and Thrust though

.
I would love to also try
DSLiveWeather. The problem is that I think Ninty dropped the ball a bit and didn't allow WPA or WPA2 security. I refuse to downgrade my router to an unsecure WEP password so I am unable to go online at all with my DS.....or use this homebrew app. It's a pity really, as it seems like a useful app to have.
I'm also on the lookout for an opensource browser to use (my slot-2 currently contains a rumble pack, so until I change that, I'm stuck without). I tried
Okiwi but couldn't get it to work

(although apparently an improved version is in the pipeline).
Not too bad though as both my Treo and PBG4 can go online for things instead

.
I've recently downloaded
Speed tester for libfat (allows you to test the read/write speeds of your chosen microSD card) and
StopWatchDS (I have an analogue watch, so having countdown timing is a useful app for me).
I've also installed a utility called
DiagnOSe. This is a great little diagnostic tool for your DS that does things like testing your rumble pack, attempting to fix stuck pixels, testing the EEprom, testing the microphone etc etc. It's just under 1Mb in size and is one of those apps that, whilst essential, you'd hope you'd never need to use it in earnest

.
I've also added
Oil Panic DS (I had this as a Game&Watch game when I was a kid) and a homebrew game called
Everlasting Love, where you play as a monkey trying to get to the exit of a level. You need to do it in as few jumps as possible (most people manage <100 when they get used to it, my first attempt got 546

(hint, it's a musicaal beat style game, where the height of your jump depends on
when you do it)
BTW, the most comprehensive database for all homebrew I've found is
http://nintendo-ds.dcemu.co.uk/. It's just a site that has links to all the 'brew available on the web, homebrew games are listed in the left hand side and homebrew apps nearer the bottom on the right.