Let me join the conversation, since it's a good opportunity to think about it. For me it would be:
* Open-source, self-hosted
* Storing the data in some very plain format, as long as it doens't conflict with other features. In fact, I'd wish for it to be plain markdown in individual files on the disk, but (aside from performance problems) I don't imagine it being fully possible. So I'm not sure where the right balance should be, but the point is it is something to strive for, since personal notes is something that should be easily editable/recoverable within minutes in any situation.
* Clients for Android, web, preferrably simple enough API to be able to write plugins for vim/atom/whatever.
* The main document format (let's call it .note further): ok, maybe not really markdown, but something intentionally simple still. The only not-markdown feature I can remember right now that is really necessary is text coloring. Must support block-quotes and tables well. Otherwise, it shouldn't be possible to make any html document you want in the editor.
* Editor UI: pretty much one of the Evernote. Embed images by drag'n'drop (automatically copying them to the server), preserve simple formatting when copying HTML markup from somewhere (like Google Docs do).
* Even though only .note files must be editable, pretty much anything should be easily attachable as a first-class note: picture, audio-file, PDF, etc. Even if the only thing app can do with the file is to upload/download, this still should be considered as much a note as a .note file.
* Auth, obviously. I doubt it's a viable feature to build, but if I'm writing it myself, I'd eventually configure it to log-in the proper user using SSL user-certificate.
* Primary purpose of notetaking app is, actually, reading the notes, not writing them, so this should be simple. The default UI for any saved note should be read-only, w/o unnecessary buttons taking up the space on the screen (especially critical when using the phone).
* Tags attachable to every note (of any format). Search using tags. Tags can be non-ASCII. Tags must be easily searchable and editable in bulk.
* Full-text search.
* Some tags can be marked as "labels", and the label should be the only possible way to organize data: treat them approx. as Gmail does, don't clutter the app with both tree-style navigation and tags. To satisfy the user who really likes trees, treat some symbol in the label (- / |) as the separator, so that "university/biology" and "university/math" would form a tree in the UI.
* Pretty much everything else I can imagine right now is anti-feature. Simple is gold. Well, maybe some sort of versioning is actually useful, but if it's implemented it should not only "just work", but also be obvious for the user to see how it works.
* Treat conflicting changes well (for example, if you lose internet connection on a mobile). Maybe something similar to how git does it: let the use choose?
* Oh, yeah, about lost connections: caching on the clients. All cached data should always be encrypted on the disk (hm, I guess it would conflict with auth by SSL?).