Even a year ago, Ruby on Rails applications were obnoxiously hard to deploy. (And I say this as somebody who loves Rails.) But today, things are much easier. Unfortunately, I don't have any experience deploying Rails on Windows servers. I can, however, tell you about deploying on Linux.
The simplest setup is probably a Linux (or BSD machine) running Apache and Phusion Passenger. Apache should be installed by default on most Linux servers, and Passenger has a nice command-line installation tool.
For a database, I generally use MySQL, though PostgreSQL might be more suitable if you do lots of really complex queries. Again, MySQL will be installed on most Linux servers.
As for your actual deployment process, I'd recommend using Capistrano. This allows you to push updated code to your server with a single command, update your database as necessary, and even revert to an older version of your code if something goes wrong.
The advantage of deploying on Windows is that you already understand it. The advantage to deploying on Linux is that lots of people are familiar with that setup, and will be able to help you past the most common problems. If you do decide to deploy on Windows, I'd make sure that you find a good support community to answer your questions. (The more you deviate from a typical Rails setup, the more you need to know to make things work. So even if you don't end up going with the biggest crowd, it helps to find a smaller crowd and follow them.)