Ringdroid (Cut mp3s down to ringtones)
Tonepicker (Select any audio file from your phone to use as a ringtone/notification)
Google Voice (the best visual voicemail, never listen to the long list again)
Astro (A great file manager)
ebuddy (login to all of your chat apps at once like aim, yahoo, msn, etc.)
I'll try to not repeat some of the great apps people have already suggested.
xScope 6.0 browser- This is my current default browser. It has great tabbed browsing that is really easy to navigate from tab to tab without too many moves. Uses the Flash 10.1 plug-in. I highly recommend it. There is a 'lite' version so you can try it out.
AppBrain App Market- This app has a few features that make it one of my most used. It allows you to search the market with much better parameters and also lets you browse apps from your computer and install them to your phone. It's what the Market should be set up like. Honestly, I wouldn't be surprised if Google just bought the company and used it as the default market.
IMDB- Simply an IMDB.com app. It's the app I use to look up movie times, user reviews and critic reviews. Simple and clean UI.
Boston BusMap - This will be of no use to you probably, but I have to mention it because it's awesome. Shows the location of MBTA buses in Boston, great for people like me who depend on public transit.
Abduction 2/Abduction - Really fun game's. Both favorites of mine.
DSP Manager - Equalizer settings for listening to music
TuneIn Radio - Listen to pretty much any radio station (local or not). I like to listen to WEEI, but on my clock radio it doesn't come in very good, so I use this.
PicSay Pro - Fun image editing app, add speech bubbles, crop, add effects etc.
WeatherBug - My favorite weather app. Clean UI and nice widgets.
Remote Notifier - Uses Wi-Fi or Bluetooth to notify you of texts, incoming calls and battery status on your computer (Windows, Linux or Mac)
GTasks - Task list that syncs with GMail tasks, also has reminders.
Also don't forget that one of the best features of the Android Market is that you have 24 hours to decide if you like a paid app, if you uninstall it before 24 hours, you don't get charged.
I have an EVO as well and I have installed the following apps:
Adobe Reader
Air Control Lite
Aidiko
Amazon MP3
AppBrain
Barcode Scanner
BD Remote
Calorie Counter
CardioTrainer
Compass
Craigsnotifica
DoubleTwist
Google Earth
Flight Director Lite
Google Sky Map
Kindle
LauncherPro
Let's Golf
List Master
Live Holdem
Mileage
MyTracks
NYTimes
Radar Now
Redbox
Spare Parts
Spirit Level Plus
Stopwatch & Timer
Swype
Tricorder
androidcentral.com and androidforums.com are forums that have a lot of information to peruse.
If anyone doesn't know, Swype is a text input method. With swyping you trace thru the letters instead of thumb pecking. In tests, it has proven faster than other methods other than use of a regular size QWERTY keyboard which for some reason isn't available on Android phones!
My most useful on my (rooted with Froyo ROM) HTC Desire
3G Watchdog - monitors 3G usage and cuts off if you're about to exceed your "free" limit
Juice Defender/Ultimate Juice - battery saver
Google Agenda Widget - shows all my upcoming appointments
Appbrain - keeps track of your installed apps
Titanium Backup - backup ( but phone must be rooted )
Catch ( formally Banana Notes ) - Reminders/Notes
Copilot Live - standalone GPS
Geohunter - for Geocaching
Dropbox - installed on ALL my machine for file transfer.
Sipdroid - sip client
Swype - keyboard replacement. ( Sometimes ) makes things so much easier .
Brut Maps - derivative of Google maps that allows you to cache map tiles rather than download live.
And yes, there's so much out there. In the end you have to find out what works for you
I'm using a rooted Xperia X10. Here's what I've got:
1) Abduction1/2 - A fun little game and is a great way to pass the time.
2) Advanced Task Killer - I don't use it too often (http://geekfor.me/faq/you-shouldnt-be-using-a-task-killer-with-android/) but sometimes, an app freezes and doesn't close so I use it to kill the app.
3) AK Notepad - It's just a notepad app. Quite handy.
4) Aldiko - A fantasic eBook reader. You NEED to have this.
5) AndroZip - Extracts zip and rar files. Also acts as a file manager.
6) Angry Birds - ...
7) Art of Manliness - Love the website. It's where I got hooked on DE shaving.
8) AppBrain - This lets you search for market apps on your computer and it downloads them to your phone when you run the app from the phone. Quite helpful.
9) ArtfulBits aiMinesweeper - It's minesweeper!!!
10) Astro - You NEED this app. It's a great file manager.
11) Barnacle Wifi Teather (root) - Since you have an EVO which has blazing fast 4G internet, you might want to have this app. It lets you tether your computer to your phone so you can use the phone as a modem. I have a WiFi only iPad so this is quite handy.
12) Bestube - Youtube downloader.
13) Bubble - Spirit level.
14) Chess - It's Chess!!!
15) Chess clock - It's Chess...well it's a chess clock actually.
16) Compass - Name says it all.
17) Connectbot - SSH client. Not really needed, but it's to have sometimes.
18) ConvertPad - This is an awesome unit converter. Get it. Now.
19) Dolphin - There's heaps of browsers, but I quite like this one. It's better than the default at any rate.
20) Ebuddy - It's...ok...there's no group chat which is a bit of a pain. I like the clean look a lot though.
21) Fancy Widget - This isn't in the market since it's pretty much a copy of the HTC clock and was pulled down for that reason. You don't need this since your phone is an HTC anyway.
22) GeoQuiz - A fun quiz app. Another great way to pass the time.
23) Google Sky Map - Useless for me, but it's got a "cool" factor so you might as well get it.
24) Google Translate - Name says it all.
25) History Eraser - The market gets clogged up with all your previous searches and it can be a pain. Use this to clear your market search history.
26) LED Light - Turns on the LED light on your phone.
27) Live Holdem - There's a pretty big player base. It's worth it for this reason alone.
28) Mahjong - Name says it all (again).
29) MSNTalk - Another IM client. Doesn't look as good as Ebuddy, but it supports group chat.
30) OpenSpark - If you have an Xbox, this lets you see who is online, view your messages etc.
31) Photobucket - Lets you upload pics to photobucket. Useful.
32) Retro Camera - Ok app. I must admit, it's pretty cool.
33) Ringdroid - Let's you cut mp3's to make ringtones.
34) Robo Defence - One of the better games I've played. It's a fun tower defence game.
35) Rockplayer - This is a must have. As far as I know, avi and mkv files aren't supported by Android. This video player plays them so it's a must have. It's pretty much CorePlayer for Android.
36) Root Explorer (root) - It lets you explore and edit your system files.
37) ShootMe (root) - Let's you take screencaps.
38) Sketcher - It's a sketchbook app that's not really useful, but it's entertaining to use every now and then.
39) Spare Parts - This is also a must have. It shows you your battery and cpu useage and statistics.
40) Speedtest - Shows you your connection speed.
41) Steamy Window -
42) Stopwatch & Timer - Name says it all...again.
43) SuperUser (root) - YOU MUST HAVE THIS IF YOU ROOT YOUR PHONE.
44) Tallybee - Just a counting app. You may find it useful (YMMV ).
45) The Schwartz Unsheathed - It's a Lightsaber app
46) Titanium Backup (root) - VERY useful. It's does a complete backup of your apps and system files. If you flash a lot of ROMs, then you need this app. It makes life easier for you.
47) Traffic Jam - One of those rush hour get-the-red-car-through-the-exit games.
48) Uninstaller - Does what the name says.
49) Voice Recorder - There's no stock one on the X10 . Not sure about other phones.
50) XDA - An app for the XDA-developers website.
The only two I have to add is Air Horn. This is just fun to blare every now and then.
Also, Smart Alarm. This reads movements if you lay it on the bed. If you set the alarm for 0530, is will go off any time between 0500 and 0530. It waits until you are in your lightest sleep because you feel better that way than if you wake from deeper sleep. It's kind of cool and seems to work.
I also have an EVO 4G. Most of the apps I use have been listed already, so here is the ammended list:
Alchemy - This is a fun, time wasting game. The interface is minimalistic when compared to the similar iPhone game, but I like this one better.
Call block (Mr. Number) - This app allows blocking of selected numbers. Calls from their "suspected spam" list are the only ones I currently have blocked. You can adjust the settings to send the call directly to voicemail or pick-up/hang-up. You can also add numbers, block all calls from non-contacts, etc. It has good functionality.
Chrome to Phone - If you use Chrome as your browser, this is a great app. You install an extension on the browser and then can click a button to send the web page you are viewing directly to your phone.
Dictionary.com - Handy mobile dictionary. It also includes an audible pronunciation for the words.
Foursquare - A fun social network app that integrates with Facebook. Only useful if you have friends who also use it.
HomePipe Free - Remote access to home PC via phone. I don't use it often, but the functionality is great for accessing photos, music & documents when away.
Not Call Log - This app does only one thing: allows you to select where the phone goes after terminating a call. I have mine set to the home screen, rather than the default phone dialer. This prevents accidental redials.
ScanLife - 2D & 3D barcode scanner.
SMS Guard - Like Call Block, but for text messages.
WeatherBug - I like the interface and widget option a little better than the HTC Weather.
Other apps I use that have already been listed are:
AppBrain - Highly recommended
3G Watchdog - More for information than anything. The EVO data plan is truly unlimited, so there is no worry of additional charges.
+1 on the Angry Birds, couldn't believe the full version is free now. Just got my Droid X so on the lookout for good new apps. really handy one I've found is backflip. nice to have my Itunes available on the X.
Got my Galaxy Vibrant last week so my list is still pretty small.
APG
ATK
Appbrain
Barcode Scanner
Calendar Notifier
Compass
ConnectBot
ConvertPad
Dolphin
Dropbox
DeluxeMoon Lite
Google Sky
Handcent
HomeBrew Calculator
IP Calculator
Smart Measure
Weather Channel
THN (hockey news) I am Canadian after all.
CFL Mobile
Ulysse Gizmos Nice GPS app
Yellowpages
Soccer Scores
TuneWiki
LauncherPro
Thanks for all of the suggestions! I've picked up (downloaded?) a few of these already. Vignette was cool as a free trial, but I have yet to drop the coin on the full version. Angry Birds is ridiculous fun, and I've spent too much time on it already. The Kindle app is great, as well as Zedge. I'm still going through a lot of these but many of them have been very cool.
Lots of good info posted, but I didn't see this listed...
GMote - basically a remote for your PC (supports Linux). When I cable my laptop to my HDTV, you can use your android for the remote during movies or as a keyboard if you are surfing the web on your TV. Must have for me. http://www.gmote.org/
Oh, and kiss your workday goodbye. Just downloaded Angry Birds this morning.