Obviously a brewing software needs to correctly calculate and formulate recipes with correlated expected results, so if that's a universal baseline what you're really asking are what additional features are required and what additional features might distinguish one solution from another.
Mobile ready. Personally, I am not interested in desktop solutions at all. I have a smartphone as almost everyone else does, or some other form of mobile computing device. When I have an idea or if I'm out in the garage brewing, I don't want to worry about a desktop/laptop holding any portion of my process.
Calendar integration as others have suggested, so that your sessions are logged and you can receive reminders of when to sample, rack and condition.
Version control is something that is often confusing, but is necessary for any serious brewer. BeerAlchemy has a recipe/"batch 1 of recipe" hierarchy that works pretty well.
Inventory management is a great feature. Personally, beer alchemy's inventory function is nicer then BeerSmith for example, but it lacks the pricing feature built into beersmith. I don't think either one of them have implemented inventory management very well, but BeerAlchemy is ahead in my eyes.
Of everything that could be built into software, I think the ultimate "killer feature" is pretty obvious. Just take a look at the software forum here and see how many times the same questions are repeated over and over - it's quite obvious that none of these software solutions are intuitive at all at the outset.
I think the killer feature would be a system of "wizards" that would offer a common sense, step-by-step method to establish basic calibration. When you boot up your software for the first time, it should ask you "Do you want to setup your equipment?". What follows should be a very specific series of questions in order. Are you brewing Extract, All Grain or Partial? Do you have a mash tun? Is your mash tun a cooler? What size cooler? Does it have a manifold? A false bottom? A braid? Do you have a HLT? Is it a cooler, pot or bucket? Do you plan to batch sparge or fly sparge? Would you like to know the difference between them? etc.
If this was well done, it would even request you to perform physical tests to verify specific results. ie - now we're going to calculate the boil off rate of your kettle. Set up your burner in your brewing location, pour X gallons of tap water and begin to boil for X minutes. After x minutes, measure the remaining volume of water with a measuring cup and enter the number here...
I personally think that the whole point of brewing software should be to help you with your brewing. If you find yourself going to a brewing forum to help you with some software then something is very backwards.