ex-s2000-owner looking for a fun sedan replacement, has to be fun, manual tranny, reliable. AND CHEAP!! like 13k or less.

To comment on your first two:
G35 - great engine, meh transmission and clutch (in my opinion), and you might find the suspension slightly unsettling when you get the car out to 90-95% of its capability. I don't find it that stable at the edge - certainly nothing like an S2K.
Civic Si - much smaller and yes, econocar roots and slightly boyracer but lots of fun. Might be your best bet.

Also consider:
Acura TL - nice interior and sharp looking (especially last generation before "the beak" which can be replaced with a normal grill) and really strong mechanicals. Much closer to the G35.

Mazda3 - you mention the speed3 but not the standard 3 with the 2.5l - not fast enough for you? It is a fun car and well built, plus you can get a much newer one than the other models you are considering.

I know what you mean about the S2000, that rear end does have a way of stepping out (though only a short hop unless you really overcook it). Insurance costs tend to be high because of the frequency with which they are wrecked.

I also know what you mean about supposedly fun cars not being all that fun when compared to the S2000. I've been wondering about a similar combination for 15 years, and have largely come up with nothing.

Something about the first-gen G35 has always appealed to me. But it doesn't steer with the agility or precision of a good sports car. Nor does anything else in that segment. The issue with the G35's stability control is that, although it will keep a lid on oversteer, it cuts in early and hard.

An M3 feels great if you can really push it. But in daily driving the steering feels heavy and the car acts like it's bored (typical BMW this way).

One outside possibility is the first-gen Lexus IS. I don't remember a "wow" moment with this one, and the interior was oddly styled (if we want to put a positive spin on it, it had "character"). Manuals are rare, but they are out there. Sadly, the wagon was not offered with a manual, or I'd likely want one. Tight back seat.

A Mazda RX-8 delivers much of the handling of the S2000, with much better control at the limit and a much better ride, and a usable back seat. But fuel economy is poor and reliability with a lot of miles is iffy.

If you can live with a very firm suspension and cheap interior, the Mitsubishi Evo might deliver what you're looking for. Much more immediate responses than any other sedan I've driven (including the STI it competes with), and a lot of steering feedback. BUT somehow they're holding value far better than I expected. Last time I was at a Mitsubishi dealer they were discounting new Evos from $36,000 to $28,000, and they were still on the lot. But look at asking prices for used 2008s, and they're rarely under $24,000. The previous generation was even more fun but even cheaper inside. And people are asking high teens to mid-20s for those as well. To get near $13,000 you'd probably have to get a 2003-2005 with a lot of miles. And it would probably have had to have been abused. Mitsubishi can't sell many of the new ones, but depreciation slows to a crawl once the value falls below $25,000.Makes no sense, but somehow the way it is.

So I guess this puts us back to the G35.

IS 300s with manual transmissions might be rare, but they are out there. There are a few in your price range with decent miles on autotrader.com right now.