Agreed - if I remember correctly, the first user-facing added features were things like POP3, later IMAP, then google apps/domain integration which points at some serious back-end heavy lifting.
Absolutely, and it's with the Google Apps/domain integration in mind I say it needs to be pushed out of beta and have Google commit to continuous development of it.
Now that the infrastructure is solid they need to continue to really drive and improve the user interface. It's still clunky with some searches and the interface can lag a little bit with the javascript.
Also, as I think about this, the themeing is also probably a step towards allowing Apps accounts to customize how the email looks for their domain and users. I hadn't considered that when I initially posted, and if that is correct that's a feature that will DEFINITELY help them push corporate accounts.
Your Apps idea is an excellent point. As of right now, I certainly don't have the feature available in my apps account, but I don't have it in my @gmail.com account yet either. Apps accounts also don't have access to "Labs" features at the moment though, so this could take some time.
If I remember correctly, you can actually already apply some branding to a google apps account (if not for a free one then the paid-for version) at the moment, but I recall it being very limited. (just the logo, possibly)
(tangent: some bizarre modding going on here - I'd love to hear why)
