Hi there! To give the best advice we need to know what you're playing. I can give some general comments though.
* Trog is excellent if you don't mind doing without spells.
* Ashenzari is decent but a bit quirky, don't use Ash if you want to use a ranged weapon because one of the ways you get piety is by cursing your regular weapon so you can't swap to it.
* Vehumet is a good choice if you started with a "mage" background, otherwise not so much
* Kiku is a great way to get necromancy spells and a pain-branded melee weapon, thus best if you started with decent int. I like Kiku for mage backgrounds or for some of the warrior-mages.
* Nemelex Xobeh is generally good but quirky--the cards can gave negative outcomes so you need to know how to deal with that.
All the altars will appear relatively early (by floor 9 IIRC) so put your focus on staying alive and you'll have plenty of god options
If you're new, I think the simple options are best. For mage backgrounds, I suggest Vehumet, Sif Muna, or Kiku.
For warrior backgrounds, try Trog, Okawaru, Makhleb, Gozag, Yredelemnul, or Hepliaklqana.
This guide is great if you want some tips on how to survive better:
http://www.ultraviolent4.com/Guide.html(However, there's also nothing wrong with the learn-by-dying method if that's what you find fun.)