That's because halothane is a gas. For example, halothane has a high lipid solubility, which indicates it is a potent anesthetic. This is confirmed by halothane's low MAC value. Halothane also has a low blood:gas partition coefficient. Now you can think, why doesn't it simply say blood solubility? That is because it has less to do with the actual solubility, but rather more to do with the volume of the compartment (blood and brain).
Halothane has a high blood:gas coefficient; this enlarges the compartments halothane has to fill before passing into the next one. In comparison, NO has a low coefficient, which which means the compartments are not as large and it can fill them rapidly to reach the next one. I apologize for the silliness of the next example, but I think it really makes it stick:
When you use halothane, it means using big cups. So even if you start by a full initial cup, it would take longer for the subsequent cups to fill.
When you use NO, it means using tiny cups. Imagine how fast it would reach then.
Ultimately, this whole concept of blood:gas coefficient has to do with how rapid the effect is. High coefficient --> Bigger compartments to fill --> Slower onset. Low coefficient --> Smaller compartments to fill --> Faster onset.