Do we have the right to interfere on a planet which may already have life?
Nitpicking: Virus are a bad choice. Most are highly specific and reuse a lot of the machinery of the cell they attack. It's much better to send a mix of bacteria and archaea (ask an specialist to get a good combination of strands that like to live in different conditions (hot/cold, oxygen/no-oxygen, ...)). Put them inside a shell to protect them from radiation and a good shell for landing/crashing (ask another specialist for this part too), perhaps like a multiheaded interplanetary missile with many a copy of your minizoo.
Probably anything you send has enough bacterias to have a chance, unless it's super clean an sterilized. They try not to send bacterias to Mars, but I think bacterias will win. They only need a single error to get a free trip.
I remember a joke that someone said that Eukaryotes is the method that Prokaryotes use to travel from planet to planet.
Right, which is why the only rational approach to life is to literally try your best to kill everyone that isn't you.
An artificial intelligence would likely be the best bet actually, but there's a bunch of challenges there we don't actually know how to solve either. Maybe in a few decades there will be fewer unknowns at least.