Opinion for the Court filed by Circuit Judge WALD.
WALD, Circuit Judge:Petroleum Communications, Inc. and RVC Services, Inc. d/b/a Coastel Communications Co. (collectively, “petitioners” or “Petrocom and Coastel”), two cellular licensees in the Gulf of Mexico area, petition for review of two rules promulgated by the Federal Communications Commission (“FCC” or “Commission”) pertaining to cellular radio telephone regions. Sections 22.903(a) and (d)(1) of the FCC’s regulations, which became effective on January 11, 1993, delineate the service regions of existing cellular licensees and set forth the circumstances under which licensees may make de minimis extensions beyond their areas of service. Petitioners contend that the FCC adopted a consent requirement for de minimis extensions without providing adequate notice and opportunity for comment under the Administrative Procedure Act, 5 U.S.C. § 553 (“APA”); that, to the extent the consent requirement was a clarification, rather than a new rule, it has been applied in a discriminatory fashion; and that the Commission abused its discretion in defining Gulf cellular regions by fixed rather than flexible boundaries. We deny Petrocom and Coastel’s petition as to the first two counts, but vacate and remand to the FCC as to the third.
I. BACKGROÜND
A. Regulatory Framework
The FCC began regulating cellular radio telephone service in 1981, issuing rules that divided the country into cellular markets and frequency blocks. See Cellular Communications Sys., 86 F.C.C.2d 469 (1981), modified, 89 F.C.C.2d 58 (1982), further modified, 90 F.C.C.2d 571 (1982). Cellular markets are defined by reference to Metropolitan Statistical Areas (“MSAs”) and Rural Service Areas (“RSAs”). The FCC currently regulates 306 MSAs and 428 RSAs, including a single region of approximately 200,000 square miles encompassing the Gulf of Mexico called the Gulf of Mexico Service Area (“GMSA”). Each cellular licensee serves a Cellular Geographic Service Area (“CGSA”) on one of two frequency blocks within the confines of an existing MSA or RSA.
The FCC’s cellular licensing program has gone through two distinct phases. During the first phase, the Commission permitted initial licensees to define the scope of their own CGSAs within existing MSA/RSA boundaries. The Commission licensed two cellular operators, one for each frequency block, within each MSA and RSA. The Commission then granted these licensees a five-year period from the date of their authorizations to expand their CGSAs within MSA/ RSA boundaries without facing competing applications from third parties. See Cellular Lottery Order, 98 F.C.C.2d 175, 204 n. 81 (1984), modified, 101 F.C.C.2d 577 (1985), further modified, 59 Rad.Reg.2d (P & F) 407 (1985). During the second phase, the contours of which were shaped by the Docket 90-6 Rulemaking at issue here, the FCC made available to new applicants those portions of MSAs or RSAs not part of an existing licensee’s CGSA at the conclusion of the five-year period. Deemed “unserved areas,” these regions must span at least fifty contiguous square miles within a single MSA or RSA. See Second Report and Order, 2 FCC Red 2306, 2308 (1987).
*1167Prior to the rulemaking challenged in this case, the FCC required licensees to provide reliable coverage to at least 75% of the area within their CGSAs.1 CGSAs thus could encompass territory much larger than the area to which licensees actually provided reliable service. See Notice of Proposed Rulemak-ing, 5 FCC Red 1044, 1047 (1990). Because of their unique geographical circumstances, including fluctuating transmission sites and the relatively large size of the region, licensees in the Gulf of Mexico region were exempted from this 75% coverage requirement altogether, and the FCC permitted GMSA licensees to define their CGSAs as coextensive with the entire Gulf of Mexico regardless of the actual area of reliable service.
The Docket 90-6 Rulemaking significantly changed CGSA boundary regulations for all existing licensees in order, “to facilitate and expedite authorization of new cellular systems in areas of the country that remain unserved.” Second Report and Order, 7 FCC Red 2449, 2450 (1992). The FCC opened areas outside of the CGSAs as thus redefined to new applications. In April 1992, the FCC released regulations setting forth a new mathematical formula to redefine CGSA boundaries to more closely approximate areas of actual reliable service. See Second Report and Order, 7 FCC Red at 2452.2 These rules became effective on July 16, 1992. In November 1992, the FCC altered this coverage formula slightly for cellular operators in the GMSA because of electromagnetic wave propagation properties unique to water-based systems. See, Third Report and Order and Memorandum Opinion and Order on Reconsideration (“Third Report and Order”), 7 FCC Red 7183 (1992); 57 Fed.Reg. 53,446, 53,447 (codified at 47 C.F.R. § 22.903(a)). Like the formula for land-based licensees, the water-based formula required GMSA licensees to limit their CGSAs to areas of actual reliable coverage. The
Third Report and Order became effective on January 11, 1993.
The Third Report and Order also addressed the conditions under which licensees could make extensions beyond their territories. Prior to the Docket 90-6 Rulemaking, the FCC’s rules permitted an existing licensee’s service to extend beyond its CGSA and into adjacent MSAs or RSAs under two different circumstances. The FCC permitted a “contract extension” if two adjacent licensees entered into an agreement allowing their service boundaries to overlap during the initial five-year period. See 47 C.F.R. § 22.-903(d)(2) (1992). The FCC also permitted any licensee to make a “de minimis extension” into adjacent MSAs or RSAs “if such extensions ... are demonstrably unavoidable for technical reasons of sound engineering design.” 47 C.F.R. § 22.903(d)(1). The Commission required licensees to minimize interference with systems in de minimis extension areas by adjusting frequencies. These extensions were authorized on a case-by-ease basis, sometimes over the objections of the adjacent, licensee.
In its Notice for the Docket 90-6 Rulemak-ing, the FCC proposed a rule for unserved area licensees similar to that already applicable to existing licensees, requiring minimization of any radio-frequency interference that might result from de minimis extensions by the adjustment of transmission frequencies. The Notice emphasized that “[b]y this proposal [the FCC was] not adding new requirements for existing licensees.” Notice of Proposed Rulemaking, 5 FCC Red 1044, 1056 (1990) (emphasis added). The FCC adopted this interference-protection proposal for un-served area licensees in its First Report and Order, 6 FCC Red at 6204. In the course of its discussion of the requirements for un-served area licensees, the FCC noted offhand in the First Report and Order that “de min-imis extensions into another carrier’s CGSA are not permitted without the consent of the *1168other license holder.” Id. In the Third Report and Order, the Commission determined to “both modify and clarify” its policies regarding de minimis extensions for unserved area and existing licensees. 7 FCC Red at 7189. Specifically, the FCC announced in a footnote that:
We are also revising the language of Section 22.903(d)(1) of the rules [pertaining to de minimis extensions] to clarify the point that an application proposing an extension into the CGSA of any other licensee’s cellular system on the same frequency block without that licensee’s consent, or into any adjacent MSA or RSA on a frequency block for which the five-year fill-in period has expired, will be considered to be defective.
Id. at 7189 n. 31 (emphasis added). This revised provision highlighting the consent requirement for de minimis extensions applies equally to all licensees.
B. Factual Setting
Petrocom and Coastel are existing licensees in the GMSA whose CGSAs were defined, prior to the instant regulations, to encompass the western half of the Gulf of Mexico and the entire Gulf of Mexico, respectively. The boundary between the GMSA and land-based MSAs and RSAs is demarcated by the coastline.3 See Petroleum Communications, Inc., 1 FCC Red 511, 513 (1986) (Order on Reconsideration). Petitioners provide cellular telephone service primarily to oil industry employees working on drilling rigs and to boating traffic in the Gulf.
Because FCC regulations do not permit licensees in the GMSA to build towers on land, petitioners must place transmission towers on the waterborne platforms of oil and gas companies. See Further Notice of Proposed Rulemaking, 6 FCC Red 6158, 6159 (1991) (recognizing “inability of Gulf carriers to locate antenna towers on land to serve Gulf areas”). When oil companies move these platforms, petitioners must relocate their facilities. See, e.g., Letter from John Cimko, Chief, Mobile Servs. Div., to Robert M. Jackson, Esq., Attorney for Petro-com (Apr. 12, 1994) (responding to Petro-com’s petition to relocate after deactivation of oil platform on which Petroeom’s facilities were situated). As a result, the territorial coverage of GMSA licensees inevitably fluctuates and is regionally limited to areas of current oil or gas exploration.4
Along with numerous other parties, Petro-com and Coastel participated in the notice and comment process in the Docket 90-6 Rulemaking. Petrocom opposed redefining the protected service areas of Gulf licensees to be coterminous with areas of actual reliable service on the grounds that the characteristics of the Gulf of Mexico region warranted unique treatment. See Comments of Petroleum Communications, Inc., at 3-11 (Jan. 16, 1992) (citing, inter alia, inflexibility of water-based transmission sites, extra equipment costs, and dependence upon oil companies). Coastel requested that the FCC adjust its proposed formula to reflect the unique propagation properties of water. The FCC declined to address many of the issues raised by Petrocom pertaining to the unique nature of the GMSA on the grounds that they were beyond the scope of the rulemak-ing proceeding. See Third Report and Order, 7 FCC Red at 7191 n. 8. The FCC rejected Petroeom’s proposal to designate the entire Gulf of Mexico region as its CGSA, choosing instead to limit Gulf CGSAs to areas of actual rehable service. See id.
As of January 1992, the FCC had granted land-based licensees in Texas, Louisiana, Mississippi, Alabama, and Florida approximately sixteen contour extensions into the shoreline waters of the GMSA. See, e.g., Florida 10 RSA Ltd. Partnership, 6 FCC Red 4469 (Mobile Serv.Div.1991). Neither *1169Coastel nor Petroeom consented to these extensions, which were justified under the de minimis exception, 47 C.F.R. § 22.908(d)(1). Coastel applied for a de minimis extension into the territory of a land-based CGSA in March 1992. The Commission rejected Coastel’s application by letter on the grounds that the land-based licensee had not consented to the intrusion. Coastel’s petition for reconsideration of this determination is currently pending before the Commission. See Petitioners’ Opening Brief, at 18.
Petroeom and Coastel brought this action to challenge § 22.903(a) of the FCC’s regulations, pertaining to the geographical scope of cellular regions in the GMSA, and § 22.-903(d)(1), pertaining to the consent requirement for de minimis extensions. Petitioners filed their petition for review within sixty days of the release of the Third Report and Order, 7 FCC Red 7183 (1992), without first filing a petition for reconsideration. A petition for reconsideration of the Third Report and Order, filed by Cellular Information Systems, Inc. on December 10, 1992, is currently before the Commission. See Respondent’s Brief at 19-20. That petition focuses on the alleged deficiency of notice and comment in the adoption of the de minimis consent requirement.
II. ANALYSIS
Petitioners make three challenges to the FCC’s rules in this proceeding. First, they contend that the FCC promulgated a consent requirement for de minimis extensions without providing proper notice and opportunity for comment as required under the APA, 5 U.S.C. § 553. Petitioners argue that the consent requirement was not a clarification, but was in fact a wholly new provision supplementing the existing rule. Second, petitioners argue that, to the extent that the consent requirement is only a clarification, the FCC has imposed the requirement in a discriminatory fashion to petitioners’ detriment, permitting land-based licensees to intrude upon their territory over their objection. Finally, petitioners contend that the FCC abused its discretion by requiring Gulf of Mexico licensees to maintain fixed service boundaries. According to petitioners, the FCC’s formula ignores the difficulties faced by Gulf licensees, whose service areas are necessarily dependent on the situation of oil and gas platforms. We address these arguments in turn.
A. Notice and Comment
Although petitioners present an arguably viable claim that the consent requirement is indeed a new rule, rather than a clarification, we do not reach the APA notice and comment issue in this case due to petitioners’ failure to exhaust their administrative remedies. Section 405(a) of the Communications Act provides in relevant part that:
The filing of a petition for reconsideration shall not be a condition precedent to judicial review of any [FCC decision] except where the party seeking such review ... relies on questions of fact or law upon which the Commission ... has been afforded no opportunity to pass.
47 U.S.C. § 405(a) (1988). In Washington Ass’n for Television & Children v. FCC, 712 F.2d 677 (D.C.Cir.1983) (“WATCH ”), we recognized that § 405(a) codifies the judicially-created requirement of exhaustion, which holds that “courts should not topple over administrative decisions unless the administrative body not only has erred but has erred against objection made at the time appropriate under its practice.” Id. at 680 (quoting United States v. L.A. Tucker Truck Lines, Inc., 344 U.S. 33, 37, 73 S.Ct. 67, 69, 97 L.Ed. 54 (1952)). Petitioners indisputably failed to present their argument on the need for notice and comment to the FCC by means of a petition for reconsideration prior to seeking review in this court. Petitioners do not contend that the FCC actually considered this issue below. We have previously employed § 405(a) to bar objections virtually identical to that raised here when not presented first to the agency. See Action for Children’s Television v. FCC, 906 F.2d 752, 755 (D.C.Cir.1990) (challenge under APA § 553); City of Brookings Mun. Tel. Co. v. FCC, 822 F.2d 1153, 1163 (D.C.Cir.1987) (same); American Radio Relay League, Inc. v. FCC, 617 F.2d 875, 879 n. 8 (D.C.Cir.1980) (same); see also American Civil Liberties Union v. FCC, 823 F.2d 1554, 1575 n. 42 (D.C.Cir.*11701987) (suggesting same by way of dictum), cert. denied sub nom. Connecticut v. FCC, 485 U.S. 959, 108 S.Ct. 1220, 99 L.Ed.2d 421 (1988). This case presents us no cause to deviate from prior practice.
To be sure, we have read § 405(a) as an exhaustion requirement, rather than as a jurisdictional prerequisite. See Southern Indiana Broadcasting, Ltd. v. FCC, 935 F.2d 1340,1342 (D.C.Cir.1991); WATCH, 712 F.2d at 681. Accordingly, we have permitted exceptions where issues by their very nature could not have been raised before the agency, see Action for Children’s Television, 906 F.2d at 755, WATCH, 712 F.2d at 682; where it would have been “futile” for petitioners to lodge their complaints before the agency, see All America Cables & Radio, Inc. v. FCC, 736 F.2d 752, 761 (D.C.Cir.1984) (FCC “made clear” its position), Way of Life Television Network, Inc. v. FCC, 593 F.2d 1356, 1360 (D.C.Cir.1979) (on “peculiar facts” of case, remand “would be an exercise in futility”); where agency action is “patently in excess of [the agency’s] authority,” WATCH, 712 F.2d at 682; and where the Commission has in fact considered the issue, whether on its own motion, see WATCH, 712 F.2d at 682, or at the behest of third parties, see Office of Communication of United Church of Christ v. FCC, 779 F.2d 702, 706-07 (D.C.Cir.1985).
Petitioners do not fit handily within any of these recognized exceptions, and we decline the opportunity to fashion a new exception to encompass their circumstances. First of all, we have previously rejected the notion that procedural objections such as these fall within that class of issues which “by their nature could not have been raised before the agency.” WATCH, 712 F.2d at 682. In City of Brookings, we reaffirmed the principle that “procedural objections premised on the APA [are] precisely the sort appropriately raised before the Commission in the first instance.” 822 F.2d at 1163. Second, as in City of Brookings, we see no indication in the agency proceedings that the Commission was “wedded to the procedures that it employed” so as to establish “futility.” Id. Third, the violation at issue in this case is neither so clear nor so egregious as to represent a patent violation of the agency’s statutory authority. As we found in City of Brookings, “the question of the applicability of notice-and-comment procedures of the APA does not yield an obvious answer.” Id. 822 F.2d at 1164.
The final exception, for situations in which another party, or the agency itself, directs attention to the issue, merits a bit more scrutiny. Another participant in this administrative proceeding, Cellular Information Systems, Inc. (“CIS”), filed a petition for partial reconsideration of the Third Report and Order on December 10, 1992. That petition, like the briefs before us here, alleges that the Commission failed to provide notice of its intent to adopt a new consent requirement for de minimis extensions, in violation of APA § 553. The FCC has yet to dispose of this petition, but claims that a draft order is currently undergoing internal review.5 Had the Commission already completed its review of this petition for partial reconsideration, we would find the exhaustion requirement vicariously satisfied as to petitioners. See Office of Communication of United Church of Christ, 779 F.2d at 706; WATCH, 712 F.2d at 682 (citing Buckeye Cablevision, Inc. v. United States, 438 F.2d 948, 951 (6th Cir.1971)). But without the agency’s resolution of the issue, we simply cannot say that the Commission “has erred against objection made at the time appropriate under its practice.” L.A. Tucker Truck Lines, 344 U.S. at 37, 73 S.Ct. at 69. The Commission has not erred against objection at all, because it has as yet done nothing in response to the objection. The CIS petition thus cannot rescue Petrocom and Coastel *1171from the strictures of § 405(a)’s exhaustion requirement.6
In sum, we find the notice and comment issue presented in this case to be a classic example of a “question[ ] of fact or law upon which the Commission ... has been afforded no opportunity to pass.” 47 U.S.C. § 405(a) (1988). “The very purpose of 47 U.S.C. § 405 is to afford the Commission the initial opportunity to correct errors in its decision or the proceeding leading to decision.” Action for Children’s Television, 906 F.2d at 755 (quoting Rogers Radio Communication Servs., Inc. v. FCC, 593 F.2d 1225, 1229 (D.C.Cir.1978)). That purpose having been thwarted here, we decline to reach petitioners’ first claim.
B. Discriminatory Application
Petitioners’ second challenge is substantially related to their first: if the consent requirement for de minimis extensions preexisted the instant rulemaking (which is to say, if, contrary to petitioners’ first argument, the Commission did not violate APA notice and comment procedures, because the consent requirement was merely a “clarification” rather than a new rule), then the consent requirement has been applied in a discriminatory fashion to petitioners’ detriment. Prior to the Docket 90-6 Rulemaking, several land-based licensees were granted de min-imis extensions into the Gulf of Mexico over petitioners’ objection. When Coastel attempted to obtain an extension in March 1992, the Commission dismissed the application on the grounds that the land-based licensee had not consented. This, petitioners claim, is an irrational, wholly unexplained difference in treatment. To remedy this arbitrary application of the rule, petitioners ask that we deem the consent requirement inapplicable to the requests of all existing licensees.
Again we find ourselves unable to reach the merits of the issue. For substantially the same reasons discussed above, we conclude that petitioners failed to exhaust their remedies as to the issue of discriminatory application of the consent requirement by declining to bring it first before the Commission. Absent judge-made exception, the Commission is statutorily entitled to the proverbial “first crack” at this issue, and we decline to reach it at this time.7
C. Territorial Scope of Gulf Licenses
Finally, petitioners contend that § 22.903(a) of the FCC’s new rules arbitrarily confines the water-based GMSAs to existing areas of actual rehable service, thus failing to differentiate between water-based and land-based licensees despite the substantially different circumstances faced by waterborne carriers. Because FCC rules prevent water-based .licensees from placing transmission towers on land, petitioners must locate their equipment on oil and gas platforms, which *1172are frequently repositioned.8 As a result, petitioners have no permanent or definite service boundaries, and their equipment sites are necessarily limited to areas of current oil or gas exploration. Contending that the FCC’s new rule limiting GMSA licensees to areas of actual reliable service is arbitrary and capricious, petitioners ask this court to vacate the revised § 22.903(a) as it applies to Gulf licensees and to remand to the Commission so it may revisit the issue. We agree with petitioners and remand the question whether GMSAs should be circumscribed to areas of actual reliable service to the Commission for reconsideration.
Because petitioners clearly presented this issue to the Commission in the Docket 90-6 Rulemaking, this final challenge does not present the intractable exhaustion problems encountered above. In its Further Notice, the FCC invited “comments whether Gulf carriers should be treated the same as or different from other cellular licensees in redrawing CGSAs.” 6 FCC Red at 6160. Pe-trocom responded in comments dated January 16, 1992 that, because of the unique problems encountered by Gulf licensees, including total dependence on the location of oil and gas platforms, remote equipment sites, fluctuating service areas, and attendant high costs, Gulf licensees should be permitted the continued flexibility to shift their actual service areas within the Gulf and to define their CGSAs to encompass the entire Gulf region. See Petrocom’s Comments at 6-17. Petrocom also suggested that the Commission defer action on the scope of GMSAs pending reconsideration of the issue of permitting GMSA licensees to construct on-shore cell sites, but it noted that the transmitter site issue was arguably beyond the scope of the instant rulemaking proceeding. See id. at 10 n. 11.
The FCC’s treatment of the issue in its Third Report and Order is vexingly terse. The Commission did adjust the reliable-service formula for water-based systems to account for different radio wave propagation properties over water. See 7 FCC Red at 7184. Aside from this modest change, however, the Commission required GMSA licensees to adhere to the same standards for redefinition of service areas that it applied to land-based licensees. The Commission dismissed all of Petrocom’s arguments to the contrary in a footnote, contending that the carrier sought a substantive change in Commission policy concerning the use of land-based transmitters that it had conceded was “beyond the scope of this proceeding.” 7 FCC Red at 7191 n. 8 (citing Petrocom’s Comments at 10 n. 11).
Our review is governed by APA § 706(2)(A), under which we set aside agency action found to be “arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law.” 5 U.S.C. § 706(2)(A). We do not set aside agency action lightly. “The scope of review under the ‘arbitrary and capricious standard’ is narrow and a court is not to substitute its judgment for that of the agency.” Motor Vehicle Mfrs. Ass’n v. State Farm Mut. Auto. Ins. Co., 463 U.S. 29, 43, 103 S.Ct. 2856, 2866, 77 L.Ed.2d 443 (1983). Nonetheless, we intervene to ensure that the agency has “examine[d] the relevant data and articulate[d] a satisfactory explanation for its action.” Id. Where the agency has failed to provide a reasoned explanation, or where the record belies the agency’s conclusion, we must undo its action. See American Tel. & Tel. Co. v. FCC, 974 F.2d 1351, 1354 (D.C.Cir.1992).
Such is the case here. We have long held that an agency must provide adequate explanation before it treats similarly situated parties differently. See, e.g., New Orleans Channel 20, Inc. v. FCC, 830 F.2d 361, 366 (D.C.Cir.1987); Public Media Center v. FCC, 587 F.2d 1322, 1331 (D.C.Cir.1978); Melody Music, Inc. v. FCC, 345 F.2d 730, 733 (D.C.Cir.1965). But the converse is also true. An agency must justify its failure to take account of circumstances that appear to warrant different treatment for different parties. The Commission itself recognized the significant differences between land-based and Gulf-based licensees prior to the instant *1173rulemaking when it permitted Gulf-based licensees to define their service areas by reference to the entire Gulf of Mexico. In its Further Notice to this very proceeding, the FCC acknowledged that:
The Gulf has been treated differently in large part because there are no permanent population centers in the Gulf, with service being provided largely to offshore oil rigs and boating traffic.... Another reason for different treatment of Gulf cellular systems has been the inability of Gulf carriers to locate antenna towers on land to serve Gulf areas because of the potential for interference caused to land systems.
6 FCC Red at 6159. Despite the Commission’s obvious, longstanding recognition of petitioners’ unique plight, the Third Report and Order silently glosses over these differences, mandating that water-based and land-based licensees alike adhere to a uniform actual service area rule.
The consequences of the Commission’s new rule for Gulf licensees appear to be dire. Limited as they are to water-borne transmitters, petitioners go only where oil and gas sites permit. The new rule freezes petitioners’ service areas at the status quo. When oil and gas rigs are deactivated, petitioners must close up shop. If new rigs do not open within reasonable proximity to the old, petitioners effectively lose the ability to serve part or all of their service areas. A recent letter by the FCC to petitioner Petrocom confirms the likelihood of this outcome: after the rig on which Petrocom housed a transmitter was recently deactivated by the oil company, Petrocom sought relocation to another platform. The FCC denied Petrocom’s request on the grounds that the new site “appears to cover primarily new areas outside of Petrocom’s CGSA, rather than the area within the CGSA which was covered by the original cell site.” Letter from John Cimko, Chief, Mobile Servs. Div., to Robert M. Jackson, Esq., Counsel for Petrocom (Apr. 12, 1994).
We are not at all persuaded by the FCC’s argument that Petroeom’s comments were entirely beyond the scope of the rulemaking proceeding. Certainly, several of Petrocom’s comments were addressed at reopening the battle over allowing GMSA licensees to place transmitters on land. Petrocom itself conceded that these comments were arguably beyond the scope of the instant action. However, the FCC altogether overlooks Petro-com’s more critical, clearly articulated point: given the inability of Gulf licensees to place transmitters on land, Gulf service areas should not be frozen at their current dimensions. The FCC utterly distorts the record to suggest that this point somehow is nonre-sponsive to its solicitation of “comments whether Gulf carriers should be treated the same as or different from other cellular licensees in redrawing CGSAs.” Further Notice, 6 FCC Red at 6160.
We remand this issue to the Commission with instructions to vacate § 22.903(a) insofar as it applies to GMSA licensees pending reconsideration. We do not foreclose the possibility that the Commission may develop a convincing rationale for applying a uniform standard to water-based and land-based licensees. We state simply that, after considering the record before us, we remain unpersuaded that the Commission has given due weight to factors bearing sharply on the wisdom or fairness of such a uniform standard.
III. Conclusion
For the foregoing reasons, we deny the petition as to counts one and two, pertaining to the de minimis consent requirement, because petitioners failed to exhaust their administrative remedies in accordance with 47 U.S.C. § 405(a). We grant the petition as to count three because we find that the Commission arbitrarily and capriciously failed to justify its decision to delimit the service areas of Gulf licensees to areas of actual reliable service.
Vacated and remanded.
. Under FCC regulations, a "reliable service area” is an area "within which the reliability of communication service is 90 percent, i.e., the area within which nine out of eveiy ten calls initiated by the base station can be satisfactorily received by the mobile unit.” 47 C.F.R. § 22.2.
. Specifically, the formula yields “the radial distance from a cell transmitter site to the boundary of its service area as a function of antenna height above average terrain (HAAT) and effective radiated power (ERF). The service area of the cell is the area within this service area boundary.” 7 FCC Red at 2452.
. Coastline is defined as " 'the line of ordinary low water along that portion of the coast which is in direct contact with the open sea and the line marking the seaward limit of inland waters.'" Petroleum Communications, Inc., 1 FCC Red 511, 513 (1986) (quoting Submerged Lands Act, 43 U.S.C. §§ 1301-1315).
. Coastel indicates, for example, that there is no oil or gas exploration off the coast of Florida east of Pensacola. Accordingly, Gulf carriers have not been able to provide cellular service to a significant portion of the Florida Gulf coast. See Comments of RVC Servs. Inc., at 15 (Jan. 16, 1992).
. We must assume that this order will be promptly forthcoming. Petitioners' counsel at oral argument revealed that one factor motivating his decision to seek immediate judicial review rather than agency reconsideration was the massive delay involved with the latter alternative. The agency has already spent almost a year and a half on this petition. We sympathize with counsel's point, urge the Commission to put an end to this impasse, and point out the availability of relief if our assumption of a prompt decision proves wrong. See, e.g., Telecommunications Research & Action Center v. FCC, 750 F.2d 70, 76-77 (D.C.Cir.1984) (examining this court’s "important role” in compelling agency action that has been improperly withheld or unreasonably delayed).
. We note that the existence of a pending petition for reconsideration on this issue does not render the agency action nonfinal with respect to petitioners. In BellSouth Corp. v. FCC, 17 F.3d 1487 (D.C.Cir.1994), we reiterated the widely accepted principle that "finality with respect to agency action is a party-based concept.” Id. at 1489 (quoting United Transp. Union v. ICC, 871 F.2d 1114, 1118 (D.C.Cir.1989)). Generally speaking, when two parties are adversely affected by an agency's action, one may petition for reconsideration before the agency at the same time that the other seeks judicial redetermination. See American Farm Lines v. Black Ball Freight Serv., 397 U.S. 532, 541, 90 S.Ct. 1288, 1293, 25 L.Ed.2d 547 (1970); West Penn Power Co. v. EPA, 860 F.2d 581, 586-87 (3d Cir.1988). This case, of course, presents the exception: a party may not simultaneously partake of judicial review if the agency has never had an opportunity to pass on the issue.
. We note that there may be another reason for refusing to address the merits of this discriminatory application issue. At bottom, this challenge addresses the application of the rules to petitioners, rather than the actual rulemaking itself. The November 9, 1992 denial of Coastel's de minimis extension application, which petitioners cite as evidence of their disparate treatment, is currently under reconsideration by the Commission at Coastel's urging. We have long found it "plain that a pending petition for rehearing must render the underlying agency action nonfinal (and hence unreviewable) with respect to the filing party.” United Transp. Union v. ICC, 871 F.2d 1114, 1116 (D.C.Cir.1989); see also BellSouth Corp. v. FCC, 17 F.3d at 1489 (D.C.Cir.1994), TeleSTAR, Inc. v. FCC, 888 F.2d 132, 134 (D.C.Cir.1989). It would seem imprudent, to say the least, to pass on the discriminatoiy application issue in this related case when the allegedly discriminatoiy decision is nonfinal and may be altered by the FCC at Coastel's behest.
. FCC rales do permit GMSA operators to build land-based cell sites if land-based licensees consent. As far as the record before us shows, however, no land-based licensee has provided such consent to date.