Given that CO binds to hemoglobin in the bloodstream almost immediately, does it follow then that one usually gets the symptoms of CO exposure almost immediately as well, once the brain is no longer getting the same O2 amount?
Presumably some effect would start immediately, I’d guess severity would depend on the amount of CO in the air.
Although I can’t speak medically, I can speak from personal experience: About 15 years ago I helped a friend remodel the basement in the home they’d just moved into. After we started in the basement we got a little light-headed quickly and in about 15 minutes we both developed splitting headaches. We actually didn’t connect any dots then and we toughed it out and kept working for a couple hours.
Coincidently he had a standard “pre-winter” furnace inspection done a week later. Turns out the heat exchanger was cracked and leaking CO. The tech said he was stunned they hadn’t died in their sleep.
So my vote is is that its consciously noticeable in less than 15 minutes.
Life lesson learned.
The symptoms will also vary with the person: one of the things that make CO poisoning or any other form of oxygen deprivation dangerous is that a frequent symptom is sleepiness. You get a bit of CO poisoning, start getting sleepy, take a nap and it becomes your last nap ever.
We had a gas fire that had just been serviced and clearly wasn’t behaving properly (yellow flame, bad smell). I borrowed a gas detector from work and it went off immediately, but there were no health symptoms.
You have an open flame unit in your house and you don’t have a CO detector? In the 21st century? You some kind of luddite or what? 
I got rid of our CO detector. The constant beeping and flashing light kept giving me a headache.
Exposure to CO at low (but dangerous) concentrations may not cause immediate symptoms. This is why canaries were used in coal mines for a long time: they were quicker to show symptoms of CO exposure than miners, allowing the miners to evacuate before problematic exposure.
Here’s a chart showing symptoms of CO exposure, along with time to onset of symptoms. The OSHA 8-hour exposure limit is 50 ppm, i.e. that’s the most someone is allowed to be exposed to on the job. Once you get a little above that concentration, you’ll be getting a headache after a couple of hours of exposure.
That addresses the question of how fast symptoms develop after the start of exposure to CO, but you asked the more interesting question of how symptoms correlate to blood concentration. I am not a doctor - I’m speculating here - but I think that at low concentrations (<1000 ppm), all/most of the CO in a lungful of air gets absorbed into the blood. Assuming the blood was hitherto untainted by CO, the now-tainted blood leaving the lungs isn’t compromised enough to cause symptoms - which is why it takes more lungfuls of air, and recirculation of the blood, to allow that blood to absorb enough CO to cause symptoms. at higher concentrations (> 1%), untainted blood arriving at the lungs gets loaded with enough CO to cause immediate problems when it gets to the brain; it doesn’t need to recirculate back to the lungs to pick up more CO.