Any Mesa EL34s will work.
Yes, it'll change the sound a fair bit, especially if you play at real volume. I'm gonna oversimplify here and say that in a Recto, EL34s give you more 'aggression' and 'cut', and 6L6s give you clarity, "punch", and frequency range. My experience is that if you like Recto sounds, like 90s-2000s hard rock, modern extreme metal, or you play anything that isn't 'heavy', stick with the 6L6s. If you want a more classic rock/metal sound where the guitar is sitting right in the midrange and the front of the mix, EL34s. EL34s give you some really good sounds in mid- to high-gain but they reduce the versatility of the amp.
Just in terms of personal preference, my buddy plays a Roadster but only ever uses Ch2 Brit and Ch3 Vintage. EL34s sound great there. On the ROV I used to have and the TOV I have now, I tried EL34s first but ended up with 6L6s because I've already got a couple 'real' EL34 amps and I want my Recto to sound like a Recto.
You will basically never get power tube saturation in a Recto (and you don't really want it, they're not designed for that) so that's not the issue, it's just the basic difference in voicing between EL34 amps and 6L6 amps.
