I've always gotten great service and wonderful flowers from FTD.com. It all depends on the local florist since that's all FTD is: a network of participating florists. The florists that happen to serve the zip codes that I've used have all been outstanding.

1800flowers.com, on the other hand, ships flowers out from a central location. I stopped ordering from them about a year ago when they sent my wife a dozen very tired-looking roses. My wife (also an AA Platinum) knew exactly why she got tired roses in the mail instead of fresh ones delivered at work: bonus miles. She busted my chops pretty good for that one.

Added bonus with FTD.com is that they can take a same-day order. It's too bad the locations you need have bad FTD florists. I tend to avoid Valentine's Day and Mother's Day for flower-ordering because I fear that places will skimp on quality or not show up at all...