I think it works well to go on from some established metall-y stuff and work your way from there. Atheist's Samba Briza is a nice way of seeing if you could enjoy Latino Jazz. Gordian Knot is essentially Fusion played in a slightly metal-ish way by some of the guys from Cynic and others. If you think you can go for all-out fusion, try some Mahavishnu Orchestra, but it's not for everyone.