Yahoo, MSN, ASK, MIVA, Text Link Ads...that's pretty much what see as valuable. I remember when Webcrawler was the best search engine out there...then again, I'm old.
IMHO it depends on the usage of search engines in your country. If advertising for a service in english, Yahoo, MSN and Ask are alternatives, but if you want to advertise in a local language in some European countries, Google is often the only player. In Denmark Google has a market share of about 90%, for example.
I doubt there is a worthy alternative to google. If you don't use adwords, you better go for blog advertising. Let people write about your company or about your products and services.
After Google, Yahoo is the best. Quality traffic and good conversions have been reported om this forum by many people in the past!