This question is more difficult than you might think, because everyone knows the "correct" answer, but few have actually used it in real life :-)
Well, the "right" answer would be マスター for addressing a bartender and 大将 for addressing a head sushi chef. Both マスター and 大将 imply that they're the highest ranked people (ie, shop owners), as you might have already guessed.
However, these words are almost never heard in common sushi-go-round restaurants or izakaya chains, which I've gotten used to.
マスター/大将 are heard mainly in nonchain, orthodox (and often expensive) bars and sushi restaurants. I think they sound not only formal but also friendly. If you are lucky enough to become a 常連 of one of such shops, feel free to address them using マスター or 大将.
Personally, I've been to such bars/restaurants several times in my life (usually accompanying someone elder than me). And I have always gotten away with just cowardly saying すみません or something like that — feeling that a one-shot, 青二才 customer like me was not the suitable person to say マスター or 大将 confidently. People who have a lot of experience of going to such shops may use マスター/大将 on the first visit, but I'm not very sure.