The song is Stranger in Paradise, from Kismet (thanks SonicQ. I vaguely recall that the melody was yoinked from some classical music piece.

The comic is quite good, with a level of intelligence, drama and humor rarely found in American comics. The quality of the art varies from panel to panel, but when it's good it's very good. It passes into melodrama regularly, but again, it's pretty good melodrama. "SiP" is one of the only non-underground comic books to feature female characters with realistic bodies.