There is No Silver Bullet, friend.

You can serve 100k from a toaster if you architect your application properly. With that said, you'll eventually want to add more toasters so make it easy on yourself:

• put your application behind haproxy or some other thing like varnishd
• user a persistent framework like Dancer2 or Mojo
• use a database proxy (haproxy seems to be defacto for postgres)
• (caching tip 1) read-only indexers like Sphinx can make searches super fast
• (caching tip 2) memcached or redis can provide super fast in-memory caching; each has their strengths are not mutally exclusive

That's not complete, but give you some ideas. You have to build scaling into your application. It doesn't have to be complicated or cloud based, you just need to put all the pieces together in the right way. That said, any VPS provider would work fine.