I've lost Faendal, and he has too much stuff on him to give up. I want to release him so I can go back to Falkreath and re-recruit him. It is Falkreath he's from right? I tried picking up another follower but everyone says the famous "looks like you have someone already". Anyone have an Idea what I can do? I don't want to go back as far as I'm going to have to to get him and re-do 4 hours of game.

By the way I never told him to wait anywhere...

Riverwood, actually

You don't say what platform you're playing on. If it's PC enter these two commands into the http://www.uesp.net/wiki/Skyrim:Console

prid 0001348C

moveto player

Riverwood, not Falkreath.

But to answer the question I don't think you can. In New Vegas they had a Companion dismissal thing but not here in Skyrim so I believe you are SOL. Save often is all I can say...

Ahh yes Riverwood, so anyway on a whim I waited three days and the game notated that my follower has left my service. Which is funny because I never asked him to wait anywhere.

If that is the case then go to Riverwood and see if you can find him again. If not then you will have to load a previous save.

I'm there and looking, does he hang out somewhere specific?

He works at the mill and keeps to a pretty tight schedule. You should find him near there. He does spend a little bit of time in Riverwood Trader now that Sven is out of the picture. But depending on where he was walking back from, it could take him a long time to get home. Followers are notorious for taking the long way home.