I would like to see companions, in two flavors: pets and summoned creatures.
Pets -- create a skill tree that allows us to capture and control pets. Adjust it so that pets that are close to our level, or higher, have a chance to break free and turn on their tormentor, you

Balance the pet with giving up something, like 1/2 of your HP goes to the pet for example. Make the pets controllable, like attack-stay-guard type commands.
Summoned Creatures -- like pets, except they are not captured. You cast a spell to summon a pet-like creature as a companion. These creatures have a specialty, like healing, melee, etc. So you could summon a minor healer to help you, or a minor melee to tank while you heal. Balance this ability with some loss, such as HP, sap, etc.
Adding a companion dramtically complicates and changes the experience, especially when playing solo. For those of us who frequently play alone, adding a companion makes the game a lot more interesting.
Balance it such that a player with a companion, is about as strong as the player without it. The only real advantage of the pet is the extra strategy you can use, and the extra complexity of playing.
Blackavar