I had excellent sweet treats and pizza at a seemingly out of the way, old Italian bakery a few years ago. This was not an actual pizzeria, but rather a bakery that threw some sauce and cheese on some bread dough and baked it. This was basically sold room temperature by square slices. I've been attempting to track this bakery down over past few years, without much luck. It may have been on the eastern edge of "downtown" but not sure. I don't believe is was actually part of Little Italy!
Your description sounds like either Galluci's (www.tasteItaly.com) market on Euclid Ave or Presti's bakery in Little Italy.
There is also a small Italian bakery near W25th and Fulton that sells pizza by the square. They bake the twist-bread that Galluci's market is famous for.