The Megaminx is a twelve-sided puzzle. You can get 12-colour and 6-colour versions. It is quite an intimidating puzzle.
Most of your cube algorithms can be translated directly to the megaminx. If you don't mind thinking whilst you solve a puzzle, and have already solved the cube, you should be able to finish this bad boy without too much trouble.
There are a few suppliers of megaminxes. Meffert makes them although they are often out of stock. The one in the picture is from Puzl - it needs a fair bit of puzzle lube and the odd adjustment to the screws to make it turn quickly. Be careful if you are getting these on the cheap. Some of the megaminxes I have picked up have been very badly made and feel like they will break at any moment - a well-made one will not give that sensation.
There have been a fair few custom-made larger versions - the Gigaminx and Teraminx have now been mass-produced although they are very pricey - larger versions are almost certain to follow. Meffert has a holey megaminx on sale - this puzzle is like the void cube is to the standard 3x3x3. Such products need to be made fairly well to work - be careful buying from anywhere that doesn't have a reputation for quality and read the reviews.