As far as staining and finishing the existing hardwood a different color, it's going to be challenging if the wood's been finished - which it sounds like it already has. Old finish is impossible to remove completely, and even if you can get most of it off, wood that's been finished once already no longer accepts stain well. Secondly, you can't refinish your staircase with hardwood. Stairs either are or aren't hardwood. If oak treads were painted, sure - sand and refinish them. But if you have more typical Douglas fir or pine tread covered with carpet, you can stain it, but it's not going to match the floor.
So our advice: Stick with your existing wood color downstairs and on the stairs, and decorate around it. Maybe paint the baseboard and walls other compelementary colors to bring in the shade you want, and complement with area rugs and other decor.Prefinished floors are generally a good option today, yes, but not on stairs. However, there's no reason you can't install it in the second floor hallway.