I got my father in law the little Samsung Restore... He figured out how to text and everything.
It's good because it has the keypad in the front and a slideout keyboard underneat... it's still small and it does all the basic things as well as some advanced things. He checks his email and gets navigation on it too.
p.