What would a playable chess variant with a complexity comparable to Go look like?
Simply increasing the board size is a very direct way to increase the complexity of the game, but this comes at the cost of losing playability. No human would be interested in playing chess on a 100x100 board unless the rules were dramatically different.
Actually it is not really correct to say that "simply increasing the board size [...] comes at the cost of losing playability". The complexity of Go on a board of the same size as chess (i.e. 8×8) would be not high at all, in fact less than chess according to my intuition. But it is true that there is some reason why we humans have a vague feeling that increasing the size of the Go board is not what gives Go its intrinsic complexity, whereas increasing the size of a chess board (say duplicating the pieces and putting them on two sides of a 16×16 board) makes it feel less playable. Based on a mathematical view, it seems to me that the main reason is the difference in the nature of pieces. In chess, many pieces can move from one end of the board to the other. In Go on the other hand, each piece has a fixed location and has a semi-local effect, in the sense that it can exert an effect on another location on the board only if it is in some unbroken chain of pieces that reaches over there. Also, the objective function is a global and fine-grained one in Go (i.e. territory), but a very local and coarse-grained one in chess (i.e. checkmate or stalemate of opponent king). Together, these two factors make Go scalable to large boards without losing playability (except for taking longer), unlike chess.
As you noted, simply increasing the branching factor is not desirable, because otherwise all we would have to do is to increase the board size and number of pieces! To increase the complexity but retain human playability, in a fully scalable manner, one can try to make the objective global and fine-grained, or make the pieces have more localized effects than in ordinary chess, or both. Here are some ideas:
Fine-grained objective: Remove check/checkmate/stalemate/castling, allow the king to get captured, and add an extra kind of move, to ascend any of your pieces that is at the final rank. Passing is allowed whenever there is no valid move. The goal is simply to ascend more pieces than your opponent.
Semi-local effect: Restrict the movement of pieces; each piece requires half a unit of energy per king step from its original location (e.g. moving a knight always requires one unit), and capturing an opponent piece requires 1 extra unit of energy, and each player has 2 units of energy per turn, except that White has only 1 unit on the first turn. For instance, on your turn (except for the first turn) you can push two pawns one step each and move a king twice, or you can move a queen one step (0.5 units) and use a pawn to capture an opponent piece (1.5 units).
These two ideas can be used separately or together, and they can clearly be tweaked in innumerable ways to smoothen or sharpen the game play. For example:
Smoother (1): Break ties in number of ascended pieces by comparing how many moves were taken to ascend the last ascended piece. A tie is still possible if both players make the final ascension move at the same time.
Sharper (1): Narrow the focus by changing the goal to count only the number of ascended pawns, while other pieces cannot be ascended.
Smoother (2): Increase the (square) board size by a factor of k and the number of pieces by a factor of m and simultaneously increase the number of units of energy available per turn by a factor of k×m. It is obvious that this is just making the army and the board more continuous, and the game mechanics retain the same flavour as the original (2). But this will greatly multiply the branching factor (more than exponential in k×m). Setting (k,m) = (2,2) should make for a nice long strategy-heavy war on the board.
Sharper (2): Make the pieces have more varied distance limit per energy usage. Doing so will make the strategy sharper because the stronger pieces (like the queen in the original chess) can maneuver more easily to where they are needed, but usually are best used as supporting pieces except when they can capture and get away.
Besides increasing the board size, there are a few other mechanisms how you can increase the branching factor:
Especially the latter two mechanisms can lead to a massive increase in branching factor, and the two games mentioned also were designed exactly for the purpose of being computationally complex.
The essential difficulty in Go does not reside in anything that can be described as complexity. The rules are as simple as they possibly could be. The difficulty comes from the scoring system. If you are you are losing the struggle for control in some sector of the board, you may be well-advised not to defend it, because that may only result in more of your stones eventually being surrounded. And if you abandon that sector only when it has become obvious that you should, it will probably be too late. Therefore you must abandon calculation in favor of intuition. That is why it took so long for computers to get good at Go. And we still dont understand how they did it.
