Actually, Madeira is fairly easy to get to. There are lots of direct flights from within Europe. There are multiple daily flights from London and Lisbon - for example. Search on Kayak.com for options.