Shoe molding is a great idea. I had the same problem in my old house. There was a 3/4" gap between the end of the tread and wall. I slid a baseboard in behind the gap and then filled with a triangular trim piece....I think I have a picture here somewhere....
Ahhhh, here it is. I hope you can see the thick 3/4" baseboard running the length of the stairs, and the small triangles between each step, filling in the gap. I may add shoe molding at some point, but don't know how to go around the bullnose....