I suggest you take a look at sup (http://supmua.org/). Its goal is to transpose the gmail experience on your terminal.
I've been working with the maildirroot branch [0] which mimics the IMAP installation of GMail, so you can use a standard OfflineIMAP to sync between your computer and GMail, and still use all the power of tagging/archiving/searching on your computer.
Oh and it has a few niceties, the most important one to me being native support of gpg.
Once you've looked at sup, take a look at Notmuch (http://notmuchmail.org/), which separates the search/indexing of incoming messages from the mail composition from sending/receiving. As a spiritual sup successor, it has a few nice clients for the command line (bower?) and various editors (Emacs, maybe a vim client too)
Gmail's implementation of IMAP is quite broken (and the XMPP/Jabber one too!).
But you can achieve a local setup which rivals with Gmail by combining mutt and/or notmuch/mu and isync (mbsync). And it's quite possible to keep it sync'ed with Gmail, although there might be some rough edges.
Personally, I don't thing tags are that useful if you have a fast and expressive local search engine like notmuch or mu (xapian-based), but YMMV.
It didn't work quite like I wished right "out of the box", but it wasn't too hard to hack it to behave more according to my wishes. Three cheers for open source software!
I'm still really interested in a full mail client that supports all of gmail's features (labels, archiving, etc), and works well with Emacs.