When I was in China I used to give QN odds to a colleague who was (I would say) about 110 BCF (1480 Elo). Although when White I used to win more than 50% of the time and managed to draw most of the rest, I found it much more difficult winning with Black. Obviously the initiative is very important as without it one cannot easily make threats or create complications. With White I found that I could develop more easily and avoid contact until fully developed by playing 1. d4 rather than 1. e4. Having said that, there is a line of the King's Gambit (but I forget which one) in which it is actually advantageous not to have your QN!
Anybody have any experience of giving or accepting odds?