Hey there, Blinky!
Cheetah gave some great advice, and I second what he said. Let me put my own little spin on it, though, and add some things as well.
I don't want to put words in his mouth, but I'm guessing what Cheetah meant about "find something you love" was just what you thought. Poke around, find a sport or activity that you enjoy, and throw yourself into it! The important thing is to get out and try lots of new things. Maybe for you it will be parkour, maybe not. That's fine. It might be ballroom dance or fencing. You may try all of these things and more, love them for a while, and then discard them as your interests change. That's totally cool too. As long as you keep moving, you'll get fit.
Speaking of getting fit... 5' 11" and 155 is NOT overweight at all. You may feel as though you're overweight because you may be noticing that you lack muscle tone, but you do not need to lose weight. Those numbers look quite healthy to me. What you may need to do is lose fat while you add muscle, and that's easily done through consistent, hard work, and a good diet.
Like Cheetah pointed out, getting fit is really a matter of making consistent baby steps that add up over time. If you eat healthy food for one day, it's not going to make a large difference. But if you do it every day for a week, then a month, then a year, it will add up before you know it.
I would start with running, since you say that's something you don't mind doing. I envy you, because for me I *hate* running (although I am trying to learn to like it because it's a part of parkour training, and parkour is something I love). Run every day, even if you don't feel like it. Commit to "microactions." Break the action into the smallest possible thing. Instead of saying "I'm going to run a mile," commit to only "I'm going to run to the end of the block." Chances are, once you get to the end of the block, you'll keep going, because a half block run feels silly; but even if you don't, you at least ran a little bit, which was more than you were running before. Keep doing this every day. Build on your commitment little by little. Each day's goal should be yesterday's goal +1. And no matter what, don't give yourself a "day off." If you're starting small enough (and you absolutely should be), then you shouldn't need a day off until several days in, when the habit is firmly established. Most people make the mistake of going full bore the first day, and then they're too sore and tired to continue for several days afterwards. That defeats the purpose. Your very first goal should be to build the habit of running/working out. Then other goals can follow from there. So since your first goal is just to build the habit, then if you can gear up and run to the end of the block every day for three weeks, you've accomplished that goal, and then you can move on to new goals like building up distance and speed.
You're right that parkour requires a lot of physical conditioning that has to be built up gradually. I have been doing parkour for only six weeks now, and pretty much the only thing I can do is roll, and even those aren't terribly consistent. In the meantime I'm working on strength exercises and also building up stamina, since that's a weakness for me. Some people are very adamant about attaining a certain degree of conditioning before you do any parkour at all, and I can see the logic in that. However there is another philosophy that says that the best way to learn parkour is to do parkour, and it can be motivating to try a few small parkour movements while you're developing your strength and conditioning your body. By "small" I mean rolls, drops of about a foot in height only, some low precisions (e.g. onto curbs or parking lot stopper thingies), etc. Basically ground-level stuff. Because that way you feel like you're doing parkour instead of just "waiting to be ready to do parkour," and also are starting to build a small skill foundation in a safe way.
Probably the biggest motivating factor, at least for parkour, is to find a group of people. It can be very hard, but often the best way to find people is to tell as many people as you can what you're doing. If nothing else, you'll get people interested. Nothing wrong with being in a group of beginners. At least you can all train together. (I'm speaking from personal experience here)
What I've found is helpful too is to just go to a playground and mess around on the equipment. I guarantee that climbing up and down the jungle gym 50 times will work out plenty of muscle groups and will test your stamina and coordination. With a group this is even more fun. Come on, when was the last time you played "tag" or "hot lava"? It's a work out, let me tell you. Plus it sends a message to all those little tykes on the playground: you're never too old to play! That's a powerful, powerful thing, in the larger scheme.
Plus it's way more fun than treading away on a machine.
When you say "working out" are you talking about going to a gym and getting on machines, or using free weights? I can see how that could get boring. Instead, try bodyweight exercises, like the ones featured in the APK WODs. These tend to be more interesting/challenging because they work a lot of muscle groups at once, and they also challenge your balance and coordination. In my view, from a psychological perspective, they are also good because the exercise becomes about you and your body, not about a piece of equipment, and that sends a positive message to your body, I think.
To sum up, and to reiterate Cheetah's points, since they're pretty much the same as mine:
-Baby steps: set yourself the smallest goals you can think of (one of my current goals is to do one pullup. ONE!), not because you want to "settle for less," but because you're being realistic. No one ever sets as a goal something they can already do. Even the smallest change can take a big effort. But it can be discouraging if your goal is too hard. How can I, for example, set 5 pullups as my goal when I'm currently not able to do one? 5 is a goal for later, for me. But if I went out and tried to do 5 pullups every time, and barely got one, that frames me in failure: I didn't get five, as opposed to I'm working towards one. Does that make sense?
-Have fun! Using your body, seeing what it can do, learning how it moves, is FUN! If it's not fun, you're doing something wrong. Granted, some days you're tired and sore, and it's unpleasant; but it should still be part of a larger, fun thing. I mean, little kids go nuts on the playground at recess for a reason. They're not sitting on the blacktop knitting, for Pete's sake. Find something physical that's fun, and do it. Be okay with the fact that you'll need to look around for a bit, maybe, to find it. It's not a failing on your part; everyone is different. I adore ballet dancing. Not a lot of other people do; nothing wrong with that. A lot of those people run instead, which is something I dislike greatly.
Put your emphasis on having fun moving, not on "getting in shape."
-Do it every day. Even if it's a small space of time, even if you run one day and walk the next. Same Bat-time, same Bat-channel. Commit to every day for a week, then two weeks, then a month. Consistency is simply a matter of renewing your goal every day, to be "yesterday's goal, +1."
Regarding diet, it's kind of the same thing: One day at a time, every day. The fresher and more colorful, the better. The less you eat out of a box or a can, the better. This is much easier if you know how to cook. If not, learn. Processed food out of a box or can, no matter how "healthy" is fifteen kinds of horrible for you, at least. Veggies and lean proteins, and whole grains.
I think I rambled and repeated myself like 15 times... it's super late. You probably think I'm crazy. But I hope you found at least something helpful in here.
Good luck to you. Just remember: "Do not be afraid of growing slowly, only of standing still."
