Oski, never really thought of it that way, makes sense tho. 

RMTB, that's one nice thing about working with the military, no one thinks it's weird if you're doing pushups at work.

Glute bridges. There are several variations for these. The most basic is to lie on your back with bent knees. Then lift your hips, hold for a second, then lower. Repeat 20 times. This gets you used to the range of movement but the point is to add weights like by resting a barbell across your hips. You can also do these with one leg on the floor and one leg raised.

If you want a similar exercise without the barbell but you do have access to a Swiss ball, get in the same position but with your feet on the ball. Raise your hips then use your feet to roll the ball away from you and back. This will strengthen your core and hamstrings.

And don't shy away from using weights! I am in better shape now and feel like more of a badass than I ever did when I was just running a lot. Learn how to dominate your body weight first (full push-ups, chin-ups, inverted rows, weighted decline sit-ups) then work up to that barbell.

There's another version of glute bridges that can be done to increase difficulty without weights - also helps with any inbalances in the glutes/hips.

So once you lift your hips, straighten one leg so that the foot and leg is off the ground, paying close attention to NOT let the hip to lower at all.  Hold, put the foot back down, then repeat on the other side, and then lower your hips.  

I found this video that shows it:

http://www.dailymotion.com/video/xhjrf3_how-to-do-glute-bridges-with-one-leg-women-s-fitness_travel

Duck rover: Thanks for the great tip re: the bridges!  I'll add those to the list!  I'm not going to lie - weights scare me.  I will try to work on the body weight stuff first, like you suggested!

Good luck! You can really do a lot with bodyweight exercises. I mean, handstand push-ups are a bodyweight exercise. (Note: I am very far away from even being able to do one of these but it's a long-term goal.)

Also, if you ever want to explore the wonderful world of lifting weights, check out a book called the New Rules of Lifting for Women by Schuler and Cosgrove, and then a site by my favorite lifting coach/expert/blogger niashanks.com. Don't be intimidated by how much Nia lifts - her advice is good for noobs. She even has some free sample workouts on there, and her Beautiful Badass program is absolutely worth downloading because you get access to excellent instructional videos and plans for beginners. Note that deadlifts, pull-ups, squats, and overhead presses are awesome core strengthening exercises (once you develop a base core strength through bodyweight exercises so that you can lift additional weight with good form).

You might also consider making some of your standard core exercises more challenging by adding harder variations. For example, you can do a plank while resting your forearms on a Swiss ball, you can do a regular plank but lift one foot or arm off the floor, do decline push-ups, do a plank where your arms are on the Swiss ball but your feet are elevated on a bench (so you are horizontal off the floor but with your upper body on an unstable surface), etc etc.

I do the core workout from Portland Fit.  It's on YouTube.  They have a group in Portland, Or. and another one in Vancouver, WA.  The videos to watch are the Vancouver Fit strength training ones.  They seem easy and basically are, but if you need to do them they won't be.  These made a big difference for me.

http://www.youtube.com/user/portlandfit?feature=watch

I also do some other exercises: clamshells with theraband, side leg lifts with a theraband.  Single leg squats standing on a stool.  Bird dogs.  Another is a front plank where you do single leg raises.

Here are a few dynamic warmups from the Oregon Health Sciences University runners clinic where I went last August.  It does make a difference in the ensuing run.  They had me rock back and stretch the calf at the end of each lunge.

.http://www.ohsu.edu/health/sports-medicine/resources/dynamicwarmup%20copy.pdf

A good Core exercise that I like is lie down on your back, place your hands under your hips raise your legs about 6 to 8 inches above the ground and then move them in a figure 8 pattern. Found this on RWOL and it really works your lower abs and obliques.

Ugh I have GOT to start some strengthening stuff myself. You know it's a problem when your upper body is too weak to support you when you're foam rolling your calves lol.

 This made me LOL.  Yes, I know the feeling too.  

You guys ROCK.  Thanks for the great tips/ideas.  I really appreciate it!