I recommend you listen to spoken Japanese and Chinese on Youtube or wherever and get a "feel" for which one sounds easier to distinguish between/more comfortable/more fun to speak.
Katakana and Hiragana are absolutely no sweat. Don't let that scare you out of learning Japanese. I've only been studying Japanese for about a month and already I know all of the Hiragana, Katakana, and about 600 kanji characters.
Chinese has 9 tones from what I've heard, but I haven't studied it, so I can't really say how hard it is.
My vote would go for Japanese. ;3 It's been pretty easy so far.