[rbanffy]

The agency will advise you on go-to-market strategies. They might have staff that knows the steps you need to put it on the store. You also need a lawyer to do the trademark part and ensure all IP you created is adequately protected - you want all moats you get create around you. The very first step might be to find an angel investor that can fund those steps. Have you considered giving Ycombinator a go?