where to find some troops

[Mystic Phoenix]

Paladins are not in the game at all as hireable troops, only your character can be a paladin.

As most troops are randomized, you can never tell where you get certain troops, although you will get access to knights and horsemen later in Kronberg if you fulfill certain quests for King Mark.
I found some knights (~10-15) on freedom islands and some more in Demonis, so be better prepared to wait a long while, until you get them (unless you are quite lucky).

I don't think there is a guaranteed place for evil beholders to recruit, though. I found two places to recruit them, one was in the very last area of the game, the other one was in the mine area, where you can get to the dwarven capital.