• Windows: gvim
• OSX: mvim
• Ubuntu/Debian: apt-get install gvim
• Other: http://www.vim.org/download.php

• Vim Adventures: browser game that teaches basic controls
• Interactive Tutorial by Open Vim: interactive browser tutorial that walks you through some of the commands without letting you get too lost
• Official Tutorial: run vimtutor at the command prompt (Windows users check your install directory)
• Derek Wyatt's Vim Tutorial Screencasts: an excellent resource if you want to see more on what Vim has to offer along with good practices

See configuration directory

• Avoid the escape key: tips on how to avoid the pains of reaching for Escape, with links to instructions on repurposing your Caps Lock key in OSX/Linux or Windows.
• Vim Cheat Sheet (there are at least a million of these, search for one that works for you)
• Need help with a command or option? Try :help <command> in vim. Press Ctrl+] to navigate to a link under your cursor in the help documents.
• Steal from whoever you can! You can find plenty of well-organized .vimrc files in a dotfiles repository on GitHub. Here's mine.