Sorry to disappoint you, Mawg – but I've heard about more than one such app (you were teasing me, admit it! :). One of them is already in the answers (Endomo). As I haven't used any such app myself, I don't really feel "authorized" to write up an answer; but there are more apps alike.
E.g. Run with Map My Run – which also "comes with a community" (of claimed "30+ million members"):
Run with Map My Run (source: Google Play; click images for larger variants)
Looking at the right-most tab in the first screenshot suggests this app can show you "nearby routes", while from the description the source of this does not become clear (Edit: I've just noticed Geoff mentioned this in his answer, so maybe check with him on that). The other two screenshots show you can "befriend" other community members – so I wouldn't wonder but rather expect that at least "shared routes" from those "friends" should show up here. Just that that's nowhere mentioned.
To read more about what others think about it (apart from the comments on Play), you might wish to check one or more of these: Review 5/2012 | 3/2013; Video Demo 1/2013; Intro 2/2013.
Then there's also My Tracks, which explicitely mentions sharing capabilities:
My Tracks records your path, speed, distance, and elevation while you walk, run, bike, or do anything else outdoors. While recording, you can view your data live, annotate your path, and hear periodic voice announcements of your progress.
With My Tracks, you can sync and share your tracks via Google Drive. For sharing, you can share tracks with friends, see the tracks your friends have shared with you, or make tracks public and share their URLs via Google+, Facebook, Twitter, etc. In addition to Google Drive, you can also export your tracks to Google My Maps, Google Spreadsheets, or external storage.
My Tracks (source: Google Play; click images for larger variants)
Again, I'm not sure whether this is a perfect match – as here it's not clear if it can show "nearby routes" directly, or if you have to check them out yourself. As the first screenshot shows, it has "shared with you" routes listed, but says nothing about a "central database".
All good things in life are... free, so let me introduce inViu routes. This app is based on OpenStreetMap – and explicitely mentions creating and sharing GPS photos, POIs, and travel routes as one of its features, route planning and recording as another one. Looks most promising in this context:
inViu routes (source: Google Play; click images for larger variant)
Not only can you track your routes; you can enrich them with photos and additional information, as all three screenshots show. Deducing from the map display (having multiple "colored lines" displayed), all available routes for your current location (or rather selected map range) can be shown right in the map. Again, I'm not sure whether routes must be explicitely shared between pairs of users, or if there's some "central pool" for "public routes" (rather looks like the former). I initially said "free", but there's also a premium version available via in-app payment.
Verdict: As initially stated, I've not used any of those apps myself – so maybe I should delete my answer before posting it. None of these apps seems to fit all the requirements (I'm sure I've seen such an app, just cannot remember it – will add it if I see it again). Still I hope you find it useful. If you think it doesn't match your question and really should be deleted, let me know ;)