I recently switched to Slicehost. For me, it's exactly what I want. A flat monthly fee for a server instance and easily upgradable as needed. They provide a choice of Linux systems, and from there you're free to build as you see fit. They offer reverse dns, which is vital for running mail servers and not available on Amazon( last I checked. )