I have been riding my old Schwinn back and forth to work as much as I can manage.
I am hooked so I have started saving for a new bike.

The thing is I don't know for sure what kind of bike i want.

My commute is 10.8 miles one way with home being 200 feet higher than work.
The hills are tough but doable with my 38/16 single speed.
Winds can be very strong here in Oklahoma and have already kept me from commuting a couple of times.
Most of the way I am riding on the rough shoulder of a fairly busy divided four lane highway.

What type of bike would you use for my commute?

Something with gears. Beyond that, it's up to your own likes, tastes, and budget.

Quick Google search yielded one LBS local to you that offers both Trek and Specialized- should be able to find something that will work for whatever budget you have there.

And I know what you mean about the winds- perhaps the biggest reason why I haven't gone to SS yet...

Since winds sound like your main problem, I'd pick a road bike with drop bars so you can tuck in closer the to the bike and be more aerodynamic. And since the roads are rough, I'd pick a road bike with clearance for tires (at least 700x32 or 35). Aside from that, your criteria are pretty broad, especially considering that you're already happy with a single speed setup. I agree with no1mad that you should start by looking at what's available locally.

Have you considered something with drop bars? That would help some with headwinds. I doubt you can get very tucked down on the sidewinder.

Is the shoulder you ride on paved? Gravel grinding definitely needs different tires than a paved shoulder.

Do you anticipate becoming a lot stronger rider than you are now? If you struggle some now with 38x16 then multiple gears are probably a good idea. I doubt your current gearing is too much fun when you have a killer tail wind that you could be taking advantage of.

Do you want to do anything else with the bike other than commute?

For riding on roads I recommend a road bike.

I have been to the LBS. It is great! They also carry Raleigh.

The shoulder is paved but rough with rocks.
I am running 60psi in my front tire to keep my hands from going numb.

The way you are all talking a cross bike or touring bike would be about right.

A CX or touring bike might be a good idea, but are prepared to drop a grand or more on one from your local shop? The Specialized Tricross Triple (base model) stickers at $990, Trek's Crossrip is a c-note higher (but comes with disc brakes), the Raleigh touring models bracket the $1,000 mark (per 2012 pricing info).

I'd be looking for a steel cross bike over a touring bike. It'll be slightly more responsive and fun. Fit some nice big tires and some quality lights and enjoy the ride!

That is what has me looking at Hybrids. They can be had for half the price of a touring bike.
Every part would be an upgrade from my old bike. No drop bars though.

Hit up craigslist and buy something that looks comfy and has a triple crank.

Heck if he browses diligently enough he might be able to find a nice Cyclocross or Touring bike for a good price.

Enid, Oklahoma. Where the wind comes sweeping over the plains? 200 feet of elevation in 10 miles. He can already do the hills in a SS. A triple is overkill.

PartsMan, ride whatever you can regardless of whether it's labelled a road bike, mountain bike, hybrid, commuter, touring bike... whatever. Just as long as you like the bike and feel comfortable on it.

What hybrids were you looking at?

Also, do you have to ride on the shoulder? or do you feel if you were just a tiny bit faster you could push out into the lane?

LOL! Yeah, it's been more than 15 years since I've last ridden a bike there and although there aren't any inclines, the wind can mean the difference between doing 10mph and 40mph. But I agree... a triple would be overkill just as long as the bike's gearing covers 32 to ~100 gear inches. No need to get a bike that offers 3 different versions of roughly the same gear ratio.

A Cross bike will have a higher bottom bracket for a bit more pedal clearance if you do need or want to quickly hit the rough shoulder. Run some dual purpose tires and you would be set for pavement or the rough.

I'm not sure where you are or how mechanically inclined you are, but you might be able to find a nice used bike. I spent a week in Tulsa a few years ago and there seemed like a decent number of cyclists there so something used should be able to be found since the summer season is ending.

How about something like this Marin? Later you can swap on some dirt drop style bars to help fight the wind.

https://tulsa.craigslist.org/bik/3254665724.html

I've been looking at that Marin, but it's a bit more than I want to spend considering I already have 3 bikes to commute on. Here's another candidate that's a bit closer to the OP.

https://stillwater.craigslist.org/bik/3251631532.html

Put some slick 1.25's on it, and the aforementioned dirt drops and you would be well equipped for your ride.

If they sell Raleigh, take the Port Townsend and Roper for a test drive. They look pretty close to exactly what you need. The Roper was on my very short list when I bought a new commuter bike last winter.

I have looked into the Port Townsend. I think it would serve as good as any bike.
I just know that hybrids are going to be very tempting when I get $5-600 saved up.

Riding a converted MTB now so I don't want to do that again.