i'm about an inch taller and ten pounds lighter than you, and though my routine is far from scientific i'll try to help.
i don't do a lot of weight training outside of curls, sticking mostly to push-ups, pull-ups, crunches and what not to focus on toning, not bulking. i run about 14 miles every day, which takes me on average a little over an hour and fifteen minutes (this is all a rough estimate, so bear with me). i built up to that, but i mention numbers specifically to illustrate that you can run every day, do toning exercises when you're hanging around watching tv, and feel absolutely fine. i guess a lot of training experts will tell you otherwise, but this is the system that's worked for me thus far, and i feel fantastic.
as far as what to eat before you work out, keep it light--i try to find fairly good sized apples at the store and eat one an hour before i run. it puts me in that magic spot of not feeling like i have anything on my stomach, but not having stomach cramps ten minutes in and feeling weak from hunger pangs.
as far as your pace, it should just be something that is just beyond strenuous for you. don't sprint--your pace should be something that feels swift and put some strain on your body initially, become more difficult as you go, and your body will go through natural swings of getting energy kicks and points where you have to struggle to keep it up. if you feel bored, you're going too slow; if you feel like you're going to die, you're going too fast.
anyway, good luck man.