A virtualização não é obrigatória para a computação em nuvem, embora seja certamente muito comum. Existem vários provedores de nuvem que oferecem recursos não virtualizados. Isso é comumente chamado de nuvem bare-metal.
Por exemplo, o SoftLayer oferece uma nuvem bare-metal.
Nuvens bare-metal são, portanto, 'mais próximas' da hospedagem tradicional de datacenter, embora você ainda tenha uma API que permita provisionar recursos.
Nuvens bare-metal geralmente oferecem melhor desempenho quando comparadas a um recurso virtual de tamanho semelhante, já que não carregam a sobrecarga de virtualização.
Quanto à sua segunda pergunta, isso depende de como você define 'tradicional'.
Se você se refere a executar software internamente em um centro de dados 'nuvem' remoto, os problemas óbvios são latência e desempenho. Escolher seu provedor de nuvem com cuidado (distância ao data center, vários tipos de recursos de computação, etc.) pode atenuar isso em grande medida. Do ponto de vista do usuário, o principal problema é uma conexão com a Internet. A largura de banda limitada pode ter um efeito bastante prejudicial na experiência do usuário da maioria dos aplicativos. Além disso, alguns aplicativos têm requisitos muito restritos sobre onde os dados podem ser armazenados. Portanto, a questão de executar esses aplicativos na nuvem também é uma questão de WHERE na nuvem que eles executam.
Além disso, o software executado em nuvem, seja virtualizado ou bare-metal, terá a mesma aparência do software executado em um data center tradicional.