For Linux, I would just look at the most popular distributions. For example, Ubuntu comes with Mono by default. Right there you've got a large potential user base.
Vista+ will have .Net.
On Mac OS X, GTK# and Mono can actually be included with the app. Banshee recently released a version that does this.
For Windows XP, I just create an installer using Visual Studio Setup project and use the prerequisites feature to determine the dependencies. If the dependencies aren't on the machine, the installer can put them in for you.
.RPM and .DEB installer formats can do the same thing for you on Linux.
All, in all I'd say write the app and then work around the dependencies by writing a good installer or package.
BTW, if you don't have Visual Studio for the installer on Windows, Innosetup works nicely as well.
N8