AO is unlikely to run any faster under Linux than under XP. At least that's what most of us seem to be experiencing. The distro doesn't seem to change anything, performance-wise: the key always is your hardware config. I'm probably gonna switch from Ubuntu to Mandriva soon though, so maybe i can tell more afterwards.
Personnally, i installed AO with Cedega and later switched to Wine.
If you simply "wine" the AO installer, the whole AO folder will be installed in a .wine invisible folder: it may be handy to move it afterwards for easier access, so you don't have to type a hundred characters every time you want to launch the game from a terminal.
Unfortunately, i'm far far away from home atm, so i can't get more into details or even check if what i'm saying here is true.
On another subject: i'm sure someome already explained how tro reconfigure an AO installation for Testlive, but could someome repost the link or PM it to me please? I'd like to return to Testlive, and especially do some Linux testing there...