Excelentes escolhas, meu amigo. Bom, a resposta à sua pergunta na verdade depende muito do seu estilo de viagem. Dependendo do tempo que vc tem disponível, vc pode usar o mesmo orçamento de formas bem diferentes e ter experiências completamente distintas!
Se o seu tempo é curto e vc quer conforto com a sua namorada, vá pra Milão, pegue um trem pra Veneza e de lá um avião pra Paris, voltando de lá. Lembre-se de que lá é inverno e muito provavelmente estará nevando em Milão e em várias regiões próximas ao seu destino. A vantagem disso é que a paisagem fica ainda mais charmosa. A desvantagem é que o dia durará menos (noites mais longas), além de toda a dificuldade proveniente de tempos frios.
Se vc tem mais tempo e conforto é uma exigência secundária, pode fazer o que fiz há 10 anos atrás: minha namorada e eu visitamos Roma, Veneza, Napoli, Milao, Pisa, Monaco (Cannes fica bem do lado de Monaco, tb), Strassburgo, Paris e regressamos a Roma. Tudo em menos de 2 semanas, com orçamento mínimo (éramos 2 estudantes na época). O segredo foi comprar um passe de trem (passe, não ticket) válido pros 2 países por 10 dias de viagem (não-consecutivos). Dormíamos no trem e passávamos o dia conhecendo a cidade em que estávamos. O único conselho que dou é arrumar estadia em 2 ou 3 cidades no meio do percurso, pra descansar, cuidar melhor da higiene pessoal e curtir melhor o lugar. Mas apesar destas dificuldades temporárias de banho (vc pode ir numa pousada e pagar pelo uso do banheiro, tb, em certas cidades), a viagem foi espetacular e inesquecível! Mas isso requer planejamento prévio (vc não quer avacalhar todo o trajeto pq perdeu o ultimo trem do dia pro próximo destino). E não se engane: trens europeus são pontuais, podem ser confortáveis (com cabines privadas, leito, etc) e são muito charmosos!
Sobre preços de hospedagem, nada melhor que hotels.com ou tripadvisor (informações atualizadas e confiáveis). Alimentação: pegue o preço das coisas no Brasil e multiplique por 3. Detalhe: lá é invertido, ok? McDonalds é o mais barato enquanto sanduiches de padaria são incrivelmente caros. Passagens aéreas: não utilize empresa de viagens, o preço e a assistência em caso de mudança são muito melhores se vc comprar direto da companhia aérea. Voar dentro da Europa tb é extremamente barato, se vc achar a companhia certa (trechos por R$100 + bagagens (sim, fique atento à quantidade de bagagem pra trechos internos, pois o excesso é caro!)). Trens: procure no Google "passe de trem europa" e vc vai encontrar. Salvo engano tem 2 empresas principais que trabalham com passes de trem nestes 2 países.
Ah, outra sugestão: tudo, inclusive passagens aéreas, tende a ser bem mais barato no fim de novembro que no começo de dezembro (devido à alta temporada das festas de fim de ano), além de mais vazio (menos multidão de turistas). Garanto que vale a pena estudar a possibilidade!
Boa sorte!