With non-unique units paladins can only be countered by upgraded halberdier, heavy camels or a huge mass of arbalesters. Monks counter them in small numbers but in late game when they're massed they're almost unstoppable unless you have halb/camel in equal numbers.

Well even arbalesters get slaughtered by Paladins, unless we are able to push them behind a wall or a corner with only a very tiny attack area for the Paladins.