For instance, when i press 'I' to go into insert mode, and then use the arrow keys to move around the line, the left arrow ends up inserting the letter 'D' one line above the line I was intending to edit, the right arrow inserts a 'C' etc. Is this a server configuration thing, an SSH thing, a vim thing or what? Any advice is appreciated, I realize this is not exactly a programming question but I'm not sure where exactly else to file it.
It's a terminal type problem. The window creating the remote connection is not properly giving an understandable terminal type. Or maybe the host doesn't recognize the terminal type and is punting to vt100 or something.
The specific ssh client and platform and the host type are needed for detailed help, but once you have connected and logged in, but before starting vim, type
echo $TERM. If it's blank or corrupted, try setting it to xterm and see if vim works better.
This page says that manually setting the TERM variable is almost never a good idea, and suggests some alternatives:
Sure enough, for me, just unsetting my TERM variable fixed the problem, plus other problems like terminal colors too.