Todo-list - I use a plain text file ~/.todo with one task per line, and use "nl < ~/.todo" in my shell startup script. I don't sync them between computers as every machine has a different purpose (work, home, server, etc..). I wrote a small script to manage it all (http://git.z3bra.org/cgit.cgi/scripts/tree/todo). It's pretty simple:
the -d flag just pass the argument as "sed ${2}d", so you can use regex and all that :)

Contacts - I'm not well organized... In fact, all I have is my ~/.mutt/aliases, which is not sync either between my computers. I only have a few contacts anyway. Otherwise, all contacts are stored on my phone. I hope I'll not loose it again!

Calendar - I use markers to write all my appointments on my bay window, as I use it everyday to enter/leave my appartment. This way I don't forget them!

Note taking & storage - I use my gopher server to have my notes available everywhere. It's just a "write everywhere and publish" workflow (I have vi, git and cgo on my phone, so I can work with it too).

e-mail setups - I have two accounts: my personnal box, and my spam box. Both are setup on my phone using imaps so I can read them anywhere. Then I use mutt with imap on my desktop, for easy management (I use different folders: dev, help, friends, commands, others). I also fetch all my mails via POP3 on my server, for archiving.

Device synchronization - I don't have any good solution yet.. I wish I had one though. I need something secure, fast and scalable so I can sync my medias, but also password managers and others. The best setup for me would an automatic rsync between my server and all the devices I connect on LAN (using some passphrase or something). I don't want to use some tier service for this. I don't trust other people regarding my personnal data. I want to do it all myself.

P.S. Thanks for this post, I love this kind of content where people share actual tips abouttheir day-to-day workflow! It makes me want to do another "workflow compilation!"