[signal]

Your options really depend on your current numbers, your estimated growth and your pain threshold for scale. Starting with a single box sounds like you either have nothing right now or you're on shared hosting, does 'dedicated box' mean a physical server or a virtual one? Virtual hosting nowadays with someone like Linode or Rackspace would be a good bet, but you can find cheap(and less reputable) options on Lowendtalk.

OS shouldn't be a dealbreaker, if you're comfortable with a distro and you see it go ahead, but if price is a consideration don't let rpm vs. deb concern you too much. You can run a stackscript to get off the ground without getting your hands dirty.

Can I ask why you wouldn't use a cloud provider? Are you already off the ground in the cloud and need to change to a single box? Or do you run a wonky stack? PHPfog runs Varnish in front of their stack, it would be plenty fast and save you tons of hassle setting up and maintaining a box. I'm on their free tier and could scale up any time.