A couple of solutions I'm aware of:
1) Omniture Site Catalyst: A lot of big sites use this but it will cost you dearly. My site runs about 85mm pvs/month and they quoted me close to a million dollars a year at those traffic levels! I didn't even bother negotiating it down, even the negotiated price would still have been way more than I'm willing to pay.
2) Urchin: I don't know how similar/dissimilar Urchin is from Analytics, but the Urchin 6 software runs about $3k. This option could prove labor intensive since you would effectively be running and logging your own metrics on your own server. So the actual costs could go up (wrt to time, equipment, etc.)
There are plenty of smaller players in this space, but the problem that always comes up is, "Will these guys be around in a year?". When looking for an business solution, it's nice to know that your data won't up and disappear should the company go bankrupt.
I do wish Google would provide a paid service for those of us that could use it and would pay for it. I'm already using Google Doubleclick for Publishers for ad serving (which costs money), you'd think they'd also want to expand their other complementary offerings (like metrics).