Recommended Search Engines:

Ask Formerly Ask Jeeves and Teoma
Exalead New French search engine with many options
Hotbot Good advanced search features
Google Scholar Google with an academic focus
Google Suggest Google with keyword suggestion help
Wisenut Try an advanced Wisesearch

Specialized Search Engines:

Firstgov Official portal for U.S. Government
Google Uncle Sam Google searches govenment docs
Scirus Specializes in scientific information

Recommended Directories:

IPL Subject-grouped sites collected by Public Librarians
Infomine Academic collection of scholarly links

Recommended Meta-Search Engines:

Vivisimo Clustered results to focus your topic
Jux2 Searches Google, Yahoo and MSN simultaneously
Mamma Great searches - especially images
Dogpile Suggests alternate searches