Yang Market in Eckington is pretty cool, with a unique selection of stuff. There's also a deli there, though I've not tried it.

Not too far away (in LeDroit Park/Bloomingdale), there's also Cookie's Corner, which I can't speak for personally, though I have seen it come up in other posts. From the looks of the photos on Google, it's also got a deli.

I bet a fun excursion would be to hit up one of these two spots for sandwiches, and then take those to Crispus Attucks Park while the blossoms are poppin'. Might have to do that myself!