Sorry for the extra post, but I realized that the Google searches in the above two posts are missing something important: the name of the app! So here's what you need to do.
Suppose you want an app which works on iOS 3.0 and which contains the word "marble". Enter the following line in the Google search box:
site:itunes.apple.com/us "requires ios 3.0" marble
You will get a list of marble-related apps which work on your first-generation iPhone.
Keep in mind that this crude search will not return apps whose descriptions say they require a different iOS version; you'll need to do separate searches for those. Also, the "US" in the apple URL restricts it to that country's iTunes store. I found that was necessary.