We're in the process of making just this move right now.  We have GMail working fine and all our mails coming in and out OK.

With regards to integration to salesforce, I'd say it depends what you want to achieve.  In some ways GMail is better to use than Outlook but in others, not.

Good things

1. A GMail button next to relevant emails throughout much of the system.
2. For an organisation the size of yours, I'm assuming that you will go for the pay version of Google Apps.  If you do, then you can automatically Google documents to your projects, cases etc.  This is pretty good - especially as Google's document sharing and collaboration is superb (NB: Their desktop apps are nowhere near as fully-featured as other spreadsheets and word processors.)
3. Google chat is superb (though I am still hammering the help to pursue the salesforce claim that chat histories are stored in context - not in my copy they ain't).
4. Google Apps themselves are excellent and can save a great deal of money.  That is, however, not pertinent to your question so I'll not pursue it further.
5. Email-to-case and our salesforce email address work superbly - absolutely brilliantly - for forwarding, copying or capturing email sent to contacts.

Things to note

1. Google Apps will take up tabs etc and may count to your limits.  I didn't check this in detail as we necessarily use Ultimate Edition but if Google does count in terms of your allowable tabs etc then it may turn out to be a much more expensive purchase than fifty bucks per year.

Bad things

In this section of my reply, first please note that not all of our support questions have been answered by SF yet sosome of these things may change.

Second, we are an IT company with a very geographically diverse customer base.  We develop software for ourselves and also on behalf of customers and other software houses.  We therefore rely heavily on email and chat etc towork with customers.

1. Outlook "Create Case" in under user control.  Not so in GMail.  Yes, there is email to case etc but this is not properly controllable (see later).
2. Add email to case is similarly absent, replaced by email to case again.
3. I said above "Email-to-case and our salesforce email address work superbly - absolutely brilliantly - for forwarding, copying or capturing email sent to contacts." Yes but not to cases!  I've driven myself nuts trying to forward an email to a case and absolutely cannot get it to work.  It is possible we're missing the point here - or a simple item of setup.  However, if you work like us where you need to create and add to cases from your email client investigate the impact of this feature.
4. Synching contacts andcalendars appears to need an add-on.  Again, this add-on was not mentioned in the SF online demo so watch out for additional objects, tabs and, possibly, cost.

Despite these problems we're having I am not regretful that we've gone down the Google route.  After all, SF and Google constantly make new releases and I expect solution to these issues in a release or two.

Good luck.