Quais são as melhores dicas para ter o seu aplicativo no Android Market e na loja de aplicativos?

Não há fórmula para isso. Mas há algumas coisas que te aproximarão.

A primeira coisa seria seguir as orientações específicas de design do Google e da Apple para seus respectivos aplicativos. Tanto a Apple como o Google estão tentando promover seus estilos de design (Flat e Material), então seguir essas diretrizes efetivamente chamará a atenção, pois é uma forma de promover "Boas Práticas".
O mesmo com algumas funcionalidades de Software/Hardware, se você usar o toque 3D para o seu aplicativo iOS de uma forma inteligente que pode fazer com que você seja apresentado como ele's algo que eles're tentando promover (Há uma categoria "Apps que usam o Toque 3D").

Outra coisa que você pode fazer é procurar no LinkedIn pelas pessoas responsáveis pela revisão dos seus aplicativos da sua categoria no seu país. Seja apresentado e finalmente escreva um email frio com um pequeno tom do seu aplicativo, porque é diferente do que's já existe, etc.

Criar um buzz no lançamento. Mesmo que você tenha feito uma bela aplicação mas ninguém a baixe, você não será apresentado. Você tem que criar aquele buzz de pelo menos 10.000 downloads por dia para ser notado. (cerca de 25k downloads por dia o colocariam no top 50 de aplicativos).