I wouldn't get a Victoria on the basis that there are other more exciting varities - Victorias are easy to buy in the shops, whereas other varities aren't. I discovered the delights of unusual fruits when my mum ought a house with a Morello cherry tree inthe garden - they are sour cherries great for cooking, amd making cherry brandy. I have one of those now and also have a 3-year old quince - true quince, Cydonia - I have two beautiful fruits about to ripen, and am looking forward to apple and quince pie. In our old house I got enough one year to make some jam as well. Much more fun!
I used to have a blue tit and majories seedling, the blue tits were by far the tastier fruit and more beautiful tree, however the majorie far exceeded it in quantity. Most plums benefit from a partner, but are reliably self fertile. It's not essential by any means. As you are considering two and already have a Victoria (again heavy fruiting) I would choose the blue tit.