Here is a source for a free dataset (Excel format) that maps zip codes and timezones as well as states and cities of course. Zip code is a good choice for granularity for matching to time zone and daylight savings changes because of special cases like the state of Indiana where different counties decide whether or not to observe daylight savings.
As far as implementing with this data: Read your FedEx API carefully. This has to be explicitly spelled out in their documentation. I'm guessing that all you really need to do is study up on the topic. Don't rush it. Take your time because you want to get this right the first time. I've been on several projects as a junior dev where the mgmt ignored timezones and paid a steep price later.
To get you started: Zulu time is a synonym of sorts for GMT and UTC, terms which all mean the similar thing and tend to be used interchangeably. When used, they mean that whatever date time is in question is somehow relative to a common point of reference which happens to run through Greenwich (and thus GMT = Greenwich Mean time.)
Whatever you do, however you store your data, make sure that you can always calculate zulu/utc/gmt from the value, or better yet, store zulu and just adjust the display for the client's timezone. There are several ways to go. Here is one. It's Sql Server specific but the concepts and strategies should be mappable to any type of db or persistent storage you're using.
For the last part of question, you should store both times individually. The word between implies two values and that's the right way to do it. Besides being more complete, this type of solution will help you address the case of "what if the start time is at 11:00 pm and the end time at 2:00 am on a daylight savings switch?"
Good luck!
P.S. Here is an interesting little read in an SO article. It's for the MS stack but interesting nonetheless and backs up some of my assertions. E.g. better to store the UTC/GMT and then convert... But read through the answers, they all have some valid points and are brief.