Amazon has recently begun offering free instances of most of their services. They announced that beginning November 1, 2010 they will be offering a free Linux "micro" instance and other services. So there you go for the Linux side, how's that for "least expensive"? :-) Then on the Windows side you'll need to buy one of their micro instance.
Or, if you already have a Windows or Linux machine at home or work, you could install something like Virtual Box and create your own Linux and Windows virtual machines for doing this testing. If you don't need them publicly accessible, this will be a very inexpensive way of doing your testing. Alternately, there are other choices like VMWare Server or VMWare ESXi (requires installing in place of an OS, so requires a dedicated machine, also requires a Windows machine to manage it), Proxmox VE, or Ubuntu includes a "personal cloud" install option that I've never used but I believe allows you to create your own cloud infrastructure like EC2 on your own hardware.
I recommend Virtual Box primarily because it was the only virtualization system that I could find that you could install on a Windows machine (Linux is also supported) that doesn't require any licensing fees for creating a new virtual machine.