To the OP;
Your suggestion seems decent and well thought out, but it'd likely focus even more of the game play strategy on using units that a ) don't die easily, and b ) gain experience, something that's already being practiced more often due to frigate-based fleets giving obscene amounts of exp. to opposing Titans.
On Titans in General;
I think they should restart at level 1 too, but they also need to be completely re-balanced so aren't as game-changing as they are now. I like the idea of them being defined as "heavy" capital ships. Not game changing units that can usually take on an entire pirate base at level one with minor support.
Sins isn't even a 4X anymore, considering how little you can actually exploit/be diplomatic with opponents, and how much focus is on building the biggest, baddest fleet. The Titan addition just shifts more and more of the game's focus on being offensively based in your gaming style.
I don't currently see any compromises to be made with the current system. If they keep their levels, destroying one doesn't mean as much, but reducing levels seems cumbersome and completely wiping their experience means the person that lost one will be annihilated. There's no second chances. Even if you gave rewards to the victorious fleet, I doubt it'd keep the other person from churning out yet another lvl. 10 Titan.