Seriously, if your looking at a Pro Tools setup, be it LE, M-Powered(M-audio) or even going HD....GET A MAC!
I actually use the M-powered version and it works quite nicely on my Mac Book. No latency issues and I've been able to daisy chain my interface with a "non-compatible" interface to give me 16 channels.
Everytime I've used PT on a windows box it seemed buggy, clunky and somewhat un-natural.
As for CS4....I think with the recent release of CS5, you will see that its a lot more stable on a MAC. I have CS 4 and have no big complaints with it. All Adobe products are very memory intensive programs, so rendering video or working with RAW files are going to chew up processor and memory pretty quick!
I guess the question I have for you, is what is the intended purpose of the machine?? Are you gonna multi-track record on it everyday? Edit video? Do graphics and photo editining? All of the above??
My advice is to get as much computer as you can for your budget. If you have to buy hardware and software in your $3500, you will end up with way less computer.
Think about what you want to do the most with and go from there. Macs are not cheap but well worth the money IMO.