Do you run from battles very often? Because I've never really found myself underpowered for that part of the game (eve my first time through). And I don't know what you mean by a high enemy encounter rate? FFVI is actually among the lowest of the 2D games in my opinion. Try FFI or IV if you a real brutal encounter rate (assuming you haven't played them. If you have then disregard this).