What is more important your battery, charger or charging regiment? Nope you probably guessed wrong.
Here is my .0002 so take it for what it's worth. After spending several years working part time at West Marine the number 1 reason for a bad battery return was the recharging routine boaters used to recharge their batteries. Mose never hooked them to a recharger. Others use an improper types of charger or wrong methods of charging. Thus they killed their batteries but we would replace them. I tried to educate them but most knew more than me. :

Funny how I would see the same few folks every 8-12 months with a battery with dead cells.
Anyhow, here is what I suggest;
1. RECHARGE Before and AFTER EVERY TRIP! No ifs and or buts. Unless you are a charter Capt. who books 200 plus trips a year chances are that your boat sits idle more than it runs. Many times minor power draws from electronics will slowly drain your batter. If your boat will sit for a long while charge the battery with the proper charger. This brings me to number 2.
2. If you are going to buy a deep cycle or mixed cycle battery then buy the proper charger. If your going to maintain batteries for a long period of time you need a three stage charger. Stage 1 is the rapid or bulk stage where about 80% of the batteries charge is replaced. The stage 2 is the absorption stage. This stage takes longer than stage 1 but lowers the current to try to replace the last 20% or so of the charge. Then stage 3 which is called the float or top-off charge. This can talk several hours and helps to condition the battery and replace the charge to 100%. If you are not using a three stage charger you are killing your batteries and wasting money.
3. Battery. Odyssey makes an incredible product. There are not bones about it. They are military grade and because the technology is not a wet cell battery you can mount it most anywhere and in most any direction... do not try this with a wet cell battery it will leak! AMG or Gell Cell batteries also don't suffer from gassing like a wet cell. You WILL pay more! But I have seen Odysey batteries last over 5 years with proper maintenance and still going strong.
If you don't want to go with an Odyssey battery then you want to look for two things. First if this is only for a trolling motor/house accessories and not starting go deep cycle. Period end of story. Yes the are a little more but it's well worth is. Second get the largest you can fit. On my previous skiff I ran a 55lb 12V trolling motor and used a Group 31 West Marine (Dekka) Wet Cell battery. That was, as Brett says, the best bang for the buck. The trade off was weight...
I could go on for hours about batteries. There is just so much misinformation out there. I hope those three point which are in order of importance as far as I'm concerned, help.
Cheers
Capt. Jan