I don't use it on my site, but recently I've noticed a couple of sites I've been visiting lagging with the status at the bottom 'waiting for google-analytics.com'. It doesn't always happen, but when it does it's very apparent. In theory any stats engine that worked on the same principal may have the same problem.
Definitely Google Analytics. If you are coming from a position where you have nothing, Google Analytics will give you everything you need. It's free and it's easy to setup, very very easy indeed.
As I said, it will give you everything you need only if you are coming from nothin. Should you later find that you need more advanced details then you can look for something else, by which time Analytics will havbe given you a decent benchmark from which to move forward. Probably not beneficial to start installing scripts and paying for stuff in the beginning.