DuckDuckGo

We are working on auto-complete (also known as auto-suggest or type-ahead), though in the meantime (and in any case) you can get DDG + Google Suggest by Nathan Friedly (open source), which adds Google's autocomplete feature to DuckDuckGo.