I'm of a mixed mind on what to recommend. Part of me says "if it were me, I'd get the Teres two-forty series and the RS-A1 tonearm, just based on hype and hearsay. Something about the mass and balance of the Teres, and the lack of mass and the swiveling head (and unipivot total simplicity and thus ultimate tweakiness) of the RS-A1 seems like a great match. I'd love to hear it sometime.
In reality, I must say that the Xerxes with the plinth sag fixed, while probably not the equal of the massive Teres, or even the Nottingham SpaceDeck (which has a better platter), isn't a glaring weak link by any means. The fiscally responsible thing to do is re-tune the Xerxes and spend your money on the tonearm and cartridge first, and then upgrade the table after you've gone as far as you can go in those other directions.
I learned about the fix for the sagging plinth on the Analog Asylum forum (check it out at http://www.audioasylum.com). Someone there posted that Gene Rubin of Gene Rubin audio had turned him onto the simple fix. I contacted Gene, and he very generously spent 5 minutes on the telephone describing the operation. He then added me to his e-mailing list and now I get notices of new releases of mouth watering British gear as they come out. Didja know you can spend a nearly infinite amount of money on a Naim rig? Here's how the conversation went:
"The fix is real simple: go down to your hardware store and buy a steel bracket, rectangular in shape with 3 or 4 screw holes going down each side. Pick up some short wood screws too. Take your platter off and take your plinth off and flip it over. Roughly in the middle of the slot (i.e. equal distances from each end) screw that bracket in nice and tight so that it pulls the sagging middle part of the plinth up to the level of the rest of the plinth. Reassemble and you're done!"
"Hey - my tonearm wiring harness prevents me from easily removing the top plinth. Can I put the bracket on top of the plinth?"
"No, it will rub against the platter when it spins".
"OK. Thanks for your help".
Then I bought my bracket and, ignoring Gene's advice, took a chisel and cut a hole in the top of plinth the exact size and depth of the bracket. I then mounted the bracket on top of the plinth and used a sharpie pen to color the bracket black. One of these day's I'll use some black enamel paint to make it really attractive (hah). I figure I haven't lost that much value on the used market because I still have the old SME holed plinth from the original owner.
So, now assuming you do this and can balance your pods and everything and you're happy with your deck, how to tweak the arm/cartridge combo:
1) Buy a new cartidge. This is a deep and wide subject. If you're wedded to moving magnet, go with one of the wood bodied Grados (avoid the two bill Sonata and go at least to the Platinum or Reference/Master). TAS really like the Ortofon Super OM-20 & 30 (but the 20 was preferred). This is under 2 bills. You'll get really happy if you do a moving coil but you've got to have the right phono stage. In the real world (under $1400) check out Benz Lukaschek PP-1 ($1350), Phonomena PP&BPS ($1200), Lehmann Black Cube ($600). You could also (and should) buy these used, or a used ARC PH1, 2, or 3. (the 1starts at around $500 used). There's cheaper too - Creek and Gram come to mind.
Once you have the step up stage, you're ready for your killer cartridge. I own the Monster Sigma Genesis 2k which I've seen NOS for two hundred and is definitely recommended at the price. I really love the Dynavector Karat. It's $750 new and is definitely a giant killer. Ortofon makes some wonderful MCs under a grand. Lyra Lydian is also in this under a grand range. I prefer to buy cartridges new, since if something goes wrong with a used unit you're on your own. On the other hand, if you can live with it (the possibility of loss), it can get you into a better class of cartridge.
2) The arm. When looking at the arm issue, the RB300 comes up as a great arm. I'd be tempted to tell you to stick with it, maybe rewire it (Origin Live style - but I'd use VanDenHul silver).
If you are dead set on upgrading the arm, the world is your oyster (the firm Xerxes will support all kinds of arms). How about that scary highly regarded RS-A1 arm (read http://www.enjoythemusic.com/magazine/equipment/0701/rslabs.htm)? They are $950 from http://www.sakurasystems.com (actually it isn't there today, have they stopped carrying it?), but apparently you get them direct from Japan from a dealer there for $550 or $600. The swiveling head simulates the geometry of a linear tracking arm, apparently reasonably well. You can buy the head shell by itself to plug into a standard head-shell bearing arm (like the SME 309 etc..). Sounds like the poor man's Naim Aro.
I've always had a soft spot for the ClearAudio Souther linear tracking arms (I'm a great believer in the linear tracking concept), but have been too afraid of the tight tolerences to get one. The Souther has the best geometry of all, but the design micro-tiny tonearm (about the size of toothpick) makes it scarily tweaky. When done right, this is probably the best arm on the planet even though it has a mechanical bearing. They come up on Ebay for around $500 from time to time in their older incarnations. How about the ET2? Hard to find, but not impossible. They aint cheap because of the excellent resale value, and they're tweaky and tough to set up (you'll need an air pump and surge tank and somewhere far from the turntable to put them. The air bearing, when fully pressurized, is about as smooth as it gets.
Speaking of smooth and perfect tonearms. The best pivoting straight arm bearing is the little length of monofilament cord dangling about a Well Tempered Turntable arm. Since the whole Well Tempered thing is so synergistic as a system, the recommendation is to find a used Well Tempered Turntable (I've seen 'em go less that a grand) or buy one new, c'mon the company need our support. These are killer rigs.
To sum up. The order of priority:
1) Keep the table and arm (tweak the table with the sag fix and the arm with new cable) and spend the money on a lovely cartridge and phono pre-amp if necessary.
2) Keep the table and get a new arm and cartridge. Dare to try the RS-A1?
3) Whole new rig. Well Tempered? Nottinham Space Deck? Teres?
Good luck out there! Let me know how it goes.