If you cannot get a reservation at the CBQ, then go for the Navy Lodge as mentioned by S. Wilkins. It's about a mile from the base and near the intersection that has DeAngelos.
Motel 6 will have the convenience of being across the street from the base, but it is, for some odd reason, built across from the water treatment/sewage plant. On certain days, that area will smell like roses.
I was stationed in Newport for 4+ years (departed Aug 2000), so feel free to ask me any questions because I may be able to help out.