Часто имеет смысл связываться с издателем ещё на начальной стадии разработки игры - они могут дать очень много ценных советов - и по жанру, и по гейм-дизайну, и по технической составляющей. Но во многом это также зависит от самого издателя. Мне приходилось работать как с хорошими, так и не очень.
В хороших могут выделить вам профессионального менеджера, который будет давать очень много ценных советов по улучшению игры, могут финансировать проект, могут сделать локализацию на множество языков и тщательное бета-тестирование (без дополнительной оплаты). При этом заберут до 70% дохода от игры (но тут всё индивидуально - насколько они подключены в разработку, объём работы и др. - может быть и значительно меньше). Как пример - Алавар. Опыт работы с ними очень положительный, но процент весьма высокий взяли.
В некоторых же не занимаются ничем, кроме продвижения. Берут ваше приложение, тестируют в течении нескольких часов на паре устройств, запихивают в стор и начинают продвижение по своим каналам. Забирать могут 50% дохода. Не так давно имели отрицательный опыт с таким издателем, в итоге сменили его на другого. Конкретных названий, простите, не имею права назвать.
Некоторые крупные издатели, вроде BigFishGames, могут вообще не заинтересоваться вашей игрой, так как им интереснее работать с крупными партнёрами, поставляющими много игр.
Продвижение своими силами, без издателя, сейчас больше похоже на лотерею - шансы есть, но они достаточно небольшие. В общем, советую сначала определиться с рынком, на который будете выходить (страны, платформы, возрастные категории и т.п.), далее - начинать поиск издателя с учётом определённых ранее критериев. Обязательно ищите отзывы тех, кто уже работал с этим издателем и смотрите на опытность издателя - сколько игр они уже выпустили, сколько из них успешны и т.д. Например, глупо будет продвигать через издателя какой-нибудь шутер, если он (издатель) до этого работал только с приложениями для детей. А из непосредственного общения с издателем вы можете узнать диапазон их услуг и условия.