This is another case of fun vs. realism. Personally I think that execution is too much, sure the punishment for murder was nothing in previous games, well, except maybe in Morrowind where you get a death sentence after the 5k mark.
Anyway, the crime and punishment system surely needs improvement. I think the player needs to pay a larger sum of gold for a charge of murder AND be forced to do a public service, not something minor like cleaning, feeding the cattle, but something more serious like hunting a nearby wild animal, a bear for example, something that is too dangerous for the guards themselves.
If the player dies then it's an honorable death and his name is cleared. If successful, however, then he would have done the city a good favor and his crime is forgiven.
Just a suggestion