Easiest way to make a hermaphroditic is to take any normal connector and place two side by side -- one male and one female. You could do this with standard pin headers/sockets, or any of your typical molex/amphenol/whatever board-to-board connectors. The other option is to create a 'bridge' component that connects two identical connectors. The simplest example of this would be to use flat-flex connectors, and then the cable is the bridge. You could also use vertical pin headers with small 'bridge' boards that have two pin sockets on the bottom. A little clunky, but cheap and effective. Depending on how the bridge is constructed it could also act as a cross-over cable to avoid having to double up some of the connections.
The two big problems are going to be insertion force and registration. Anything that requires lateral force to insert is going to be difficult to assemble without disrupting the other tiles. It will also be quite difficult to insert a tile in a slot that already borders 2 or more other tiles. If you don't have anything that gives, you are going to have problem with registration. The more tiles you add, the more alignment errors in the individual connectors add up and will make new pieces not mate perfectly on every edge.
I am not a fan of using magnets as the actual contacts. Without some springiness, it will be quite difficult to make sure they make contact, at least if you have more than 1 or 2 "pins". On the other hand, using magnets to hold the pieces in place could work fairly well. How about a row of pogo pins and pads, with a pair of small rare earth magnets on either side to hold it together. You will still want some mechanical guides to provide lateral alignment, but they don't need to be a tight fit. Make sure you get N/S oriented consistently!