Are you having the same problem listening to other peoples songs on Soundcloud?
Regardless what format you upload in, soundcloud will convert them to it's own format for playback, in theory as I understand it, everyones music should be streaming at the same size/time.
For quality purposes, I would suggest uploading to souncloud in a lossless format such as .wav or .aiff, rather than mp3 if you have the option.
That's the highest quality and will suffer the least from the compression that Soundcloud applies.
Yodasdad