Oh, how I miss the magnifying glass search tool on my Palm!
For Droid - I use PowerSearch (free) to search the entire Droid, and Calendar Companion ($1.99) to search your Google Calendar that's stored online (not just what's in your droid). With Calendar Companion, you can only search for one word phrases.
Since I like to read texts immediately when I get them (as I would think most people do), I was pretty surprised that the default Text Messaging app did not have an option for the texts to "Pop up" as you received them. Luckily, Handcent SMS (free) does just that. The interface also looks a bit more like the Iphone text messsaging.