If not ledges, why not have some fabric that hangs down - that you can flip up with your feet and then put your shoes on. When it flips down, the dirt will be facing the underside of the seat.
Okay, so that would send out the message that it's okay to put feet on seats - but so many people do it, you're never going to stop them doing so. That is unless we issue on the spot penalties, but look at the fuss when that happens from the 'haven't you got anything better to do' brigade that seem to have such a loud voice (when they should be slapped in the face!).
If you take your shoes off then I don't consider it to be a problem - unless you have smelly feet! Likewise, putting your feet up on an old newspaper that is fully open - and then moving before being asked if someone else gets on the train.
Personally, I prefer to sit upright. In fact, I usually sit up or forward (usually on my phone!) and don't even lean back into the seat!