I highly recommend finding yourself a good real estate broker and having a loan pre-approved before shopping there. Best bet is to look at schools first, and then figure out an area where you want to live.
As I said, the market there is extremely volatile.....the house I bought had only been on the market for four hours and had two other offers on it, in addition to mine. (Mine won out because I did not ask for a contingency for selling my house, despite the other two bidders offering higher prices for the property.)
Hickory High School is currently the top-rated high school in the Tidewater area, but the Virginia Beach schools of Cox, First Colonial, and Kellam are also good (and Cox is usually the top HS in all of Virginia!)
If you are trying to get to Oceana, try and stay close to NE Chesapeake....because otherwise it will be a hellish-commute and is far worse than anything I experienced commuting from Scripps Ranch to North Island (back in 99!) while in San Diego.
As for avoiding Norfolk and NOB, a ships company billet will put your significant other over the top for the Chief's and LDO selection boards. It worked for me!