I'm not a native speaker or a great speaker at that, but I've always heard 海边 and not 海旁边. Perhaps 海旁边 is grammatically correct but just shortened to 海边? I think this is a good question, and would be interested in an answer too, if anyone knows it.
Would any native English speakers (like me!) interpret this as "near the sea", or are people generally in agreement that "by the sea" implies directly next to the sea?
A little. You could interpret "我们的酒店就在海边" as "our hotel is right by the sea" (or perhaps even a sort of emphatic "it's precisely the case that our hotel is by the sea", depending on the context).