I am married to Camila from Riverwood, and I realised I would prefer being married to someone who acts as a follower.
I don't want to get a bounty or be confronted the guards of Whiterun whatsoever, so how do I kill her discreetly? I'm not going to slaughter her in public.
Best Answer
It sounds to me like the easiest way to do it discreetly would be to move to her house and do it there, as long as nobody else lives there. Alternately: Go to one of your houses, ask your Housecarl there to follow you. Take the Housecarl outside of the house and ask them to wait there. Then, go back to your house and kill your wife.
However, as @Mana has mentioned, you will not be able to remarry after your wife has died. The only way to possibly get around this would be with some console commands on the PC.