I might also recommend op. 27 no. 1 in C-sharp minor, which is often overshadowed by it's much more technically demanding neighbour nocturne in Db major (op. 27 no. 2); op. 27 no. 1 fits nicely into programs and is truly one of the most complex of the nocturnes, although I also wouldn't say that it's more involved, than, for instance op. 62 no. 1, op. 55 no. 2, or op. 9 no. 3 (the last of which, by the way, is also an excellent "study" in Chopin-esque ornamentations, and is technically challenging enough to put it on the top end for judging. It's also one of my faves!). Also, check out op. 48 no. 1 in c minor if you don't mind an overplayed beauty, and if you do, look no further than its vastly ignored neighbour in f-sharp minor, op. 48 no. 2, which happens to be one of the longest nocturnes as well. Haunting melody!
Be sure not to miss the op. 37's either! One is in g minor and is a piece of cake technically, but its beauty ranks it up there with my faves as well (for that matter, there is also the bizarre, yet gorgeous, op. 15 no. 3 also in g minor which is very similar to op. 37 no. 1); the second is in G major and is made a little tricky by constant interval issues in the right hand. I believe I read somewhere once that that particular nocturne used to be a lot more popular than it is today, and listening to it gives a certain feeling of being in a Parisian salon, as you might imagine.
Ahem, so, yeah the question now is which nocturnes *haven't* I mentioned?? Heh, basically I personally would avoid any of the ones I haven't mentioned, including op. 27 no. 2 which I noted on the side...
But that's just me! Don't make a decision without listening to all of them!