It's clearly an expansion problem.
Note that characters without the expansion aren't very well balanced either (but the balance is different than with the expansion).
It would be nice to balance them. Changing their powers is probably too tricky but an option to VP bid somewhat akin to what you can do in Terra Mystica would be nice.
I wouldn't do it exactly like in TM though, I would simply get a random pick of N+1 characters and then have players bid on them with VP.
The actual working of the bidding is relatively simple:
Players bid in turn order (or reverse turn order).
When it is your turn to bid, you can bid any amount of VP (including 0) on a character with no bid on it or you can overbid on one of the characters that already has a bid. When doing so, put a token of your color on the character.
If you overbid on a character, the previous bid and token is returned to the previous bidder.
As long as your last bid is still standing, your turn is automatically passed.
Once all the players have a bid on a character, the bidding ends.
Because picking last was a way to reduce the advantage of playing first, some other mean of helping players down the starting order would be welcome. It might be a simple as giving an extra gold to the second player and a pick of one gold or camel to 3rd and a jade to the 4th player.