VPS: Una máquina compartida por varios usuarios
Cluod: Básicamente algo similar a lo anterior
Servidor dedicado: Tú propia máquina para ti sólito
Para saber cual son los recursos mínimos que necesitas es preciso saber algunos datos más acerca del tipo de web y el tipo de tráfico que tiene. Hablas de páginas vistas pero no de usuarios únicos y tampoco comentas al respecto del sitio. ¿ es un blog estático con texto e imágenes? ¿ es una página de descargas? ¿ es otro tipo de herramienta? Hay una gran diferencia entre tener mil usuarios online leyendo un texto plano o tenerlos subiendo archivos y a la vez utilizando un chat, por poner un ejemplo.
Otro dato importante a tener en cuenta es el ancho de banda que consume el sitio. Si es un blog estático y bien optimizado con 40M de usuarios al mes podrías funcionar bien en un buen VPS, sin embargo, si es una página de descargas, el mayor problema no lo tendrás en el uso de CPU o memoria sino en el ancho de banda que vas a consumir.
Yo personalmente con 40M de páginas vistas al mes, e independientemente de todo lo demás, me iría directo a un dedicado. En un VPS siempre estás expuesto a los errores de tus "compañeros de máquina" y ya sólo el riesgo de perder un día de ingresos te justificará el coste del servidor dedicado. Luego, dentro de los dedicados ya dependiendo del tipo de web me decantaría por una opción u otra.