Recent large scale disasters have awakened governments domestically and overseas to their needs for preparedness to support homeland security and public safety. First responders of various agencies (e.g., fire department, police, EMS) are often on the front line to assist in managing these events to protect lives and property. The effectiveness of their mission is highly dependent on capability of communication systems available at incident scenes. The US Department of Homeland Security has among its top priorities the need for stronger information sharing and infrastructure protection, as well as interoperable communications and equipments. In this paper, we determine key requirements for first responder systems by examining various vulnerabilities and threats in such systems. We investigate implications of interoperable heterogeneous networking, horizontal/vertical communications and various applications on system architecture design. We also identify technical challenges in designing first responder systems with high quality of service and quality of protection, which are critical for supporting diverse multimedia first responder applications over reliable and trusted heterogeneous networks.