^^ What he said.
If you're serious about your workout, then upright it must be.
The recumbent ones are ok for older guys with back injuries I guess. They're definitely more comfortable, but you're not going to get the same intensity of workout as with an upright.
I know exactly what you mean about the seat getting uncomfortable after a while... But on most models you can replace it with whatever bike seat you like.
I'm thinking about giving this a try: