Short version: Somebody asked me how to create bingo cards for class. I said "I'm sure there is a program that will do that for you if you Google for it." She said: "I Googled, nothing works." That was my first indication there might be a market for this. My second, which convinced me, was that when I made something to tide her over (hacked together in 4 hours and possibly the worst software in my life I ever inflicted on other people), I got fifteen thank you letters and fifteen "I really want to use this but I can't because it is broken!" letters from a mailing list with 60 people on it. That was my first, very unplanned, exposure to the Minimum Viable Product.
I estimated the world market for my product at 2,000 teachers and thought, with a bit of work, I might eventually sell as much as $200 a month. Turns out I suck at math.
I don't know what you consider interesting about the early days of the startup. Let's see. At the time I was starting I was on a severe frugality kick and had a rigid budget every month, the better for retiring my student loans early. My budget had $60 a month allocated for video games. So I skipped the game and gave the business a $60 lease on life: it had to pay its own way after that. It has.
The music analysis stuff was really time consuming and expensive and of course wasn't nearly as good as Pandora, so I canned it, but had this left over code that crawled the web looking for music.
I did a few quick changes to the code so that it grabbed concerts instead of music, and voila, http://HearWhere.com