I remember hitting this problem in my early 20's, and it's not to be trifled with. However, there's a lot you can do. There are a number of techniques.

1. Exercise. A number of people have mentioned it, and it's a very powerful technique - it releases a whole lot of chemicals that make you happier and smarter for at least a couple of days after each session.
2. Regular routine. Sleep at a regular time, and wake up at a regular time. Have a pattern to your day where you do things at regular times.
3. Sunlight. It cheers you up right away, and has a longer term mood enhancement too. You need to be outside in it, as the UV radiation creates vitamin D, which helps.
4. Purpose. Have a plan to do one thing, and work at it. A job seems like the right one to try to me. You don't need to figure out what you'd really like to do right now - just aim for something you're qualified for and can get along with. You can get a better job later....
5. Diet. Eat food that resembles something that might grow naturally outside.

Did you know that facial expressions are bidirectional? If you smile, you'll feel happier. If you have a miserable expression, you'll feel more miserable. I don't suggest you go around grimacing (although it's worth trying that once, just to show yourself how significant the effect is), but find some reason to do something social which requires you to be publicly cheerful. And after a few minutes, it will work its magic.

Watch out for deep introspection - it has its uses, but when melancholy, it can easily chew through all your mental energy, and the benefits just aren't there. Just from your post I can tell you're fundamentally an interesting guy, and it doesn't need to be any more complicated than that. You won't answer your big life questions right now - in fact nobody tends to answer them at all. In fact I'd go so far as to say that a big part of getting out of melancholy is to stop thinking about yourself - think about things, activities - other people - anything except who you are and the meaning of life.

For mood improvement purposes, I wouldn't aim for big, deep relationships - it can work, but it often takes too much energy and it can easily all go wrong. Try larger numbers of lighter relationships. Perhaps you can join a team sports club or something like that.

Aim to get a job - nothing much else in life really goes places unless you've got some money to make it happen. Get your CV sorted out, and have applying for work as part of your routine.

And don't do it all at once - nobody can change more than a couple of habits at a time !