This is a big overlooked weakness of both Emacs and Vi(m). After about five years of using Vi I switched to a friendlier editor, NEdit; within a couple months, I was better at using NEdit than I was at Vi, mainly because of discoverability. I then used (X)Emacs for a couple of years (mainly for Python programming, though the original motivation was learning Lisp), and found it rather opaque. Now I use TextMate, and I've had the same basic experience as with NEdit.
Sure Textmate may have some keybindings, but you can't use Textmate while ssh'd to a remote server.