Holy crap! I feel behind the times now - I didn't know there was another LED size smaller than 0603! I'll have to pick up some 0405's one of these days...
To the list of suppliers I'd add Mouser.com and EBay.
David: If you decide to use SMD LEDs (which I think would be a good idea, given what you're trying to accomplish) I can offer a few suggestions on how to handle the little buggers. The trick is, until you get at least one wire soldered to 'em, they're very easy to drop and almost impossible to find again once dropped. I had to practice soldering to the little buggers before I got the hang of it. Basically, my procedure is like this:
1: Take an LED out of the packaging. (They usually come encased in a little plastic strip - you can peel off the sealing layer to remove one LED at a time) Don't lose it!
2: Get some pliers, with rubber bands wrapped around the handles. Put the LED face-up on a flat surface, and grab 'em with the pliers. Try to grab just the lens - you don't want the pliers making contact with the electrical contacts too much, or they'll sap away all the heat when you're soldering your connections.
3: Fire up the soldering iron. Get it clean and shiny, then put a bit of solder on it, smear some on one of the contacts. It should now look pretty much like the contact is silver, you don't want too much solder on there. If there's too much you can clean the iron again and use it to wipe away some solder.
4: Prepare your wire. Lately I've been using magnet wire (from Radio Shack - though they only sell it in a pack of three spools, of which only one is of a suitable size - so you may want to find an alternate source...) Magnet wire can be hard to prep, though - so you may be better off with Wire Wrap wire or stranded 30 AWG wire. Anyway, strip off some insulation from the end, without damaging the wire - then heat up the wire with the soldering iron and put some solder to it - silver the wire like you did with the contact on the LED. If it's stranded wire the solder should fuse the strands together. Wipe off excess, let it cool, then trim the exposed part of the wire very short - about 1-2mm.
5: Clean the soldering iron again, then put a bit of solder on it again - bring the wire to the contact on the LED and heat it up with the soldering iron. You don't want to add too much solder, you just want to make sure there's a good (electrical and mechanical) connection.
Right now I'm working on a project that's using some surface-mount LEDs: you can see some of my wiring
here.