From what I understand, Random Personalities add variance to each of the flavor values of each leader (IIRC was 2-3 points either side of the normal value). So in the end, you get some slight variations in each leader that are enough to make the game unpredictable, but not a simple switch of personalities as in Civ 4.
I NEVER play without Random Personalities. If you ask me, it's the way it's meant to be played. Strategy is adapting to unpredictable circumstances.