Deberías tener claro cuanto espacio en disco ocuparás entre toda tu web, con vídeos, fotos y demás, peso total, y también cuantos visitantes esperas en la misma. ¿Usarás programación dinámica con PHP-MySQL o HTML estático?
Sobre Linux y Windows.. diferencias hay muchas, pero a nivel de web hosting la diferencia principal parte por si usarás programación con tecnología de Microsoft, ej. ASP o MSSQL, ahora.. si vas a usar PHP, MySQL o HTML simple, no te molestes en contratar Windows, corre mucho mejor sobre Linux y de seguro también los planes Linux te cuestan mucho más baratos
Saludos,