I’ve personally used AT&T (now part of Cingular but I was just AT&T), Sprint and T-Mobile (current carrier). My work also makes me use a Nextel phone as a chirper.
Of all of them so far my best experience is with T-Mobile. YMMV of course.
T-Mobile has a very detailed web site that specifies signal strength down to a neighborhood level. http://www.t-mobile.com/coverage/Default.asp
Cingular has maps that show coverage but are far less detailed. http://onlinestorez.cingular.com/cell-phone-service/maps/pop_mapfinder.jsp
I suppose if you look at others you will find maps as well. Note that while you will see many uncovered areas I was told by a Sprint guy (when I mentioned it) that they cover something like 98% of the population of the United States. I may have the exact percentage wrong but it was high and the point being you generally have to be in the boonies to get no signal.
Best thing you can do is ask people in the areas you visit most often what their experiences are. For instance in Chicago there is a notorious deadzone on Lake Shore Drive that I asked others about and found it wasn’t just me.
Here is a link to T-Mobile’s PDA lineup. http://www.t-mobile.com/products/default.asp?class=pda
Here is a link to Cingular phones: http://onlinestorez.cingular.com/cell-phone-service/cell-phones/cell-phones.jsp?q_categoryId=1717200031&q_addAnotherPhone=false
You will need to look into which support Act! (be very specific on that requirement to make sure).
That said if your dad has issues with hi-tech stuff a PDA/Cell phone combo is likely to drive him nuts. By definition those PDA phones are feature rich. Not to mention I have found from my parents their manual dexterity is not so good for mashing tiny keyboard buttons (not to mention eyesight squinting at small handheld screens).
I will say avoid the Motorola Razr. I have one and while it is sexy looking showing it to my parents I found it was not good for them at all. It’s flat design, non-raised keypad made it difficult for them to handle well.
Best idea is to visit a store (any store) and let him handle a few and see if one seems to work well. Often phones can be used with different providers so once you find a phone you like find out which cell companies support it (there are differences as Sprint uses a different broadcast technology than Cingular).
If your dad travels to other countries know that you need to get an international capable phone if he wants to use it there.