512mb should be loads, assuming that you have not already filled it up with other things.
There is no official recommended software for use with Skype but since Fring is free, try it out, if you are not happy then try something else.
You could also try iSkoot which I dislike because you still incur a minimal network charge even when you are using it with your wlan.