My android gmail app is just as fast as the web. I have 35k messages, about 1.5gb. The web interface is slowish, but I haven't noticed the phone app being any slower.