Right now I have an E36 M3 and my wife drives an E39 530i. Before the five, she drove a VW TDi. Before the M3, I drove Miatas and E30's.
Who will be the primary driver for the new car - you or your wife? If you, get the four door M3 (hold out for a four door, I wish I had). If your wife, get an E39. Both cars are the best of their breeds - the E39 was the primo luxury sport sedan of its generation, and the M3 was the best sports sedan of its era.
You will love the M3 and it's amazing ability to be perfectly at home both on the street and track, but your wife will find the rear cramped and the suspension overly firm. Your wife will love the sophistication, class and spaciousness of the E39, but you will daydream of a car with more responsive handling and road feel.
TDi? Heh. They're a very practical, functional car and a terrific tuning platform for the hypermileage geeks. The MKIV TDi's were also the slowest passenger cars sold at that time and are not at all drivers cars. My wife is a little sentimental about hers (it was her first new car) but you'd have to pry her BMW steering wheel from her cold, dead fingers before she'd go back to another Jetta.
PS - Several good deals on choice E36's and E39's have come up on the Georgia board over at BimmerForums.com. A number of the more active Peachtree BMW CCA members hang out on that forum and are a great resource for local leads: http://forums.bimmerforums.com/forum/forumdisplay.php?f=176

