I have always used Evernote for note taking in class. I used it very heavily, without internet, for a long time without problems.
Evernote makes it easy to remember things big and small from your everyday life using your computer, phone, tablet and the web.
It offers a great UI and an even better back-end (syncing and such). The only downside to Evernote is that you have a monthly limit (100MB) for how much you can sync, but if you are just taking notes (text notes), you are never going to reach that limit. So rather than a storage limit you have to adherer to, you just have to watch that you don't go over 100MB per month, other than its unlimited storage.
- Very easily syncs with one account to all devices
- Has an offical app for Windows and Android but no official one for Linux. There are community created clients, such as Everpad, Nevernote or Geeknote (this one supports OS X as well)
- Able to view and edit notes offline while waiting for a connection (used this feature many o' times)
- Not sure about the checklist feature but you can create bullet points and put strike through text when you are done with them. Supports pictures and links
- Free (ad supported) with the option of getting premium
- Ability to create different note books and tags for organizational purposes
- Ability to add audio clips to notes as well as pictures and other files of your choice
- Every feature you would expect in a basic word processor (fonts, colours, formatting etc)
- Ability to "email in" a note to yourself so that if for some reason you can't access your Evernote, you can just send an email to it and it'll be there waiting for you when you get back
- Ability to take a snapshot of a webpage and save it to your notebook]
- Collaboration features
I know you talk about not wanting to use a web app but I have to mention it. Evernote has such a great web app I have never used anything in my life that is more simple as what they have created. Its so easy to use and won't cause you any hassle, ever. It is perfect if you are away from your computer/mobile device and have to access Evernote. It won't take two seconds to load up and get the information you need.