App compatibility for first gen iPod touch
You can use iOSSearch, a free tool to find apps in the iTunes store which are compatible with iOS 3.1.3. This is a non-commercial page I made.

Note: the app store has recently been updated to allow downloads of last compatible versions but it appears that this only provides apps which are compatible with iOS 4.