Gap between wall and stair treads
Small pieces of trim on each tread and each riser would do nicely to hide those gaps. They'll be pretty fiddly to get a nice joint where horizontal meets vertical - you'll want cope those joints so they stay nice looking and don't open up over time.
Based on this picture, I would agree that they're not &quot;real&quot; wood. Where that paint has come off, it looks like MDF. Even with paint on them, I'm not sure how well they'll take the daily abuse of being walked on. The carpet protected them from wear, but the paint may not take the abuse as well. If you're going to remove the carpeting, you'll probably want to replace the treads with solid wood. The risers should be OK remaining MDF, if that's what they're made of.
Also, be aware that paint can be very slippery, especially glossy paints. You'll want to look at something that's specifically designed for floors, or something that you can add some fine sand or grit to in order to give traction. You don't want increase the chances of someone slipping on the stairs, tumbling down, and landing on that tile at the bottom.