Neon, firstly I would like to say that I really like Norah and am very happy with her success. Regarding Cleo Laine, she may well be the most famous living jazz singer in the UK (go figure), but like the others here, I have to say she leaves me cold and you should in no way judge other jazz vocalists by your experience of listening to her.
I agree with Jim and would say that you owe it to yourself to give Sinatra a spin. I have friends who really like jazz and others that don't, but they all enjoy listening to Francis Albert.