I believe I have it nailed down.
Google uses items from your past searches to narrow your searches results.
The highlighted link to "Web History" (available when you are connected to Google) lets you know what kind of history information Google uses to narrow your searches down. (It can be a lot of things, but default settings only look at your past Google Searches)
After a visit to that link, a nuking of the "Web History information", and some wait time for Google to flush results from its system, results became consistent between incognito and normal mode in Chromium.
I believe that Web History is used only for people who visit Google Search while connected to a Google account. (Which will be your default state if you are a Google account user.)
After some more verification, I have confirmed that Web History is also activated by default for people who do not have a Google account (I suspect it works with a cookie). Though one cannot see what kind of information Google has without a Google account, there is a link to choose to opt-out.
NB: I believe that the only other big factor in Google's results is the chosen search language (obvious when you think about it, but it kind of bugged me before I saw that Chromium was set in English and Chrome in French).
If You Must Use Flash
Generally speaking, my understanding is that Adobe no longer supports flash in Linux - but that the Google Chrome project has decided to integrate and support flash on their own. So Google Chrome would be the only browser that you can use at the moment out of the box, so to speak.
I have managed to get flash to work on other browsers from a recent install on an older 32 bit machine by using a flash-sse plugin (Shockwave Flash 11.1 r102). This build is made for chips that do not have SSE support. I don't know what machine you are using but this is important information.
This was not on an Ubuntu machine but an Arch Linux box running Gnome, but you should be able to find an older version of flash or flash-sse for Ubuntu.
What will happen is that the newer versions of Firefox (I have v27) will block older flash versions automatically with a security warning. You will have to click Activate ... and then Allow ... to view flash. Personally I prefer this as I don't like flash adverts streaming to my machine and using bandwidth.
The security risk, if any, can be mitigated somewhat by sending file locations to &>/dev/null, so that all data streaming in will be shredded on arrival.
[update] I have just installed Chromium v32+ and the above setup (Shockwave Flash 11.1 r102) works for Chromium too - without the grumbling that Firefox exhibits.
For Ubuntu you might be able to find a Debian package that will work. A good link to follow is https://wiki.debian.org/FlashPlayer. It seems that Flash 11 is the last version to work on Linux.
Otherwise Use HTML5
Alternatively, you can enable HTML5 instead of flash on any HTML5 capable browser (especially Chromium) by following this link https://www.youtube.com/html5 and clicking Request the HTML5 Player. From this point forward your Youtube videos and some others will play on any HTML5 capable browser, but I found on my older machine this was too resource intensive. On newer machines I don't think this will be a problem. This is where all streaming content is headed anyway and is why Adobe Flash will be phased out in the longer term.
Best Answer
It seems there is some problem with the DNS resolver, as far as I can tell. Check it out what's in your /etc/resolv.conf, is it the correct nameserver you want to use? I am not sure about your problem: on Ubuntu only chromium behaves like this, or other browsers too? It's not so useful to mention that it works with windows, since maybe you have different nameserver setting in windows, that's why it works there. What would be useful is to know if other browser(s) in Ubuntu work(s) or not. If you have the issue that you have wrong nameserver in /etc/resolv.conf, you should check how you got that: it's your setting, or got via DHCP etc etc. Also you can use terminal to try out some DNS lookup to see if it works there or not, like
host www.google.com