Yeah, Christ that marching mini-game is just impossible. I don't think I've ever got more than 30% on there. I'm sure you get something decent for getting over 40-50% though I can't remember what it is.

The performance for Rufus though I'm pretty boss at (though it looked tough doing it on the HD mod, good job!) but I purposefully never get higher than 100. The Force Stealer is great but you can pick one up in Corel for 2200 gil when you get there. If you get between 60-90 on this mini-game, you get a HP Plus materia. You can't get hold of one of these until Cosmo Canyon and they set you back 8000 gil.