The theme can matter as there are a lot of things you can confure in it.
The way the menu is rendered is defined in a template that comes with the Theme.
A theme developer can manipulate the output of the menu in that template including the the issue you have.
I'm not saying that's the case here, but if I visit my sites through https, the link in the menu are rendered with https too.
On the logo:
I use the Core Logo skin object and I see this link for the logo:
<img id="dnn_ctl02_imgLogo" class="Logo" src="/Portals/0/FFLogoBlack.png?ver=n-xI6h1WXgjTMk4_LaAiGQ%3d%3d" alt="DNN9 base">
AFAIK the logo skin object normally does not include the domainnname in the logo url in DNN.
I'm testing on DNN 09.10.02, on what version do you have this issue?