How do I get enough detail to decipher what's an arm from a torso?
Simplify it. Rather than trying to make the arm look exactly like an arm with every perfect curvature and muscle and hair, just go with a flesh colored log, and use
shading to differentiate it from the torso. I say shading because if you work with "outlines" on the inside of a sprite you'll find that they, coupled with shading can quickly clutter up a sprite and take up space that could be dedicated to defining forms and colors. Generally, outlines inside sprites only make reading them harder. (Though that's not to say it can't be done tactfully and pleasingly.)
How do i fit enough animation in so you can tell it's a little guy walking?
Likewise, simplify. Rather than trying to get all the subtleties of a motion into a small sprite, try going for the larger, more general motions and maybe even exaggerating them if you're still having trouble reading them. Walk cycles are walk cycles no matter what size or resolution they are, so it might do you some good to find some tutoreals or - as I prefer to call them - guides on two dimensional walk cycles to learn the components of such before tackling the extra task of fitting it into a small grid of colored squares.
What size is recommended for my sprites? I want to go for Cave Story/Spelunky type size personally, but doubt my character designs would transition that small..
This is, I think, entirely a matter of personal preference. However you should keep in mind what you would like your sprites to represent - a realistic world would obviously have characters with realistic proportions and they would probably take up less space in a 32*32 grid than a cartoony one with proportions stretched to fill out the frame. However, if you want your character(s) to be expressive in both actions and facially, I'd suggest a more deformed style to allow for larger, more malleable features. Also keep in mind that if you're going for a realistic character in a small space you'd probably have to leave out even more details just to make it read well.
I'm scared of referencing too much from other games' sprites for animation purposes in case of imitating those styles too much :S
I wouldn't worry about this. In fact I'd encourage you to look at other games' art and animation to see what they did and how they did it. Don't worry about copying too closely - if you don't want to you won't, it's not like it's some kind of thing where you'll subconsciously come up with the exact same sprite - and ultimately you'll learn alot quicker. I'd say look at sprites and animations from a variety of styles, though, not just realistic sprites or SD sprites, to see what similarities and differences they boast and to get an idea of what is done because it's right and what is done because it's a part of that individual work.
[/two cents]
Lastly, being able to draw well traditionally is a damn fine - aught necessary skill to have that will speed up the process and improve your results ridiculously exponentially.
Good luck.