It's not a city, but in between Paris & Venice are... the Alps! It would be a nice change to have a few days of gorgeous (and highly accessible) mountains in between the cities, rather than just yet another city. You can easily take trains from Paris to the Alps, and from the Alps to Venice (I just did the latter a couple of weeks ago). I'd recommend Chamonix, Grindelwald/Lauterbrunnen, or Zermatt. On the other hand, if you're a strictly city person and don't care for mountain/glacier landscapes, ignore this suggestion.
I've had bad luck with Charles de Gaulle airport in Paris. It's just about the most poorly organized, dysfunctional airport I've ever been through. On the other hand, going through Heathrow/London and taking a ferry or Chunnel train adds a lot of travel time (unless you want to see London too), and Heathrow security people are quite draconian when it comes to enforcing carry-on rules.
Lisa
P.S. You realize that in summer Venice is hot, smelly and intensely packed with tourists? It's a wonderful and unique place, but you have to not be bothered by crowds if you go in summer rather than winter.
P.P.S. The most usable and complete European train schedule web site I've found is Germany's Deutschbahn website,
www.bahn.de . Very easy to plan trains all over Europe using it.