Refinish or replace an old staircase
Sand and Paint
Veneer or replace treads - that's a lot of work.
Carpet - relatively easy - but you said you don't want that.
Don't try to sand and stain - the level of sanding will be much more than for painting and I suspect in the end you will find so much old paint that staining won't work well.
Which leaves Sand and Paint as the best option.
No matter what you do, if the stairs are older than 1978 then test for lead paint or just assume that there is lead paint and take appropriate precautions.