I came from a TP2 to an Evo. A few differences, but not major. My contact list if just a bit over 500. With the TP2 I got in to the habit of loading everything in to the first name line, leaving the last name line blank. Doing this allowed me to search on first/last and whatever else I was able to stuff there.
The search function in Android does an ok job. I still stuff everything in to the first line by habit, but it is not really necessary. In addition, using the "People" application and the search button on the lower right does an ok job of finding things.
With the Palm I used a software package by SHSH Software called Takephone. Shimon has a similar application for Android called aTakephone at his site,
http://www.shsh.com. I enjoyed the Palm release and this one is coming right along.