<PAGE>
 
                                                                   EXHIBIT 10.22


                                   AGREEMENT

     AGREEMENT (the "Agreement"), entered into on this 31st day of July 1998,
between Prodigy Services Corporation, a Delaware Corporation (the "Company"),
and an indirect wholly owned subsidiary of Prodigy, Inc. (the "Parent"), with
its principal place of business at 44 So. Broadway, and Russell I. Pillar,
residing at 174 West 76th Street, #12-H, New York, N.Y. (the "Executive").

     WHEREAS, the Company and the Executive are parties to an Employment
Agreement dated as of September 29, 1997 (the "Employment Agreement");

     WHEREAS, on September 29, 1997, the Executive was granted an option
pursuant to the Prodigy, Inc., Stock Option Plan to purchase 625,000 shares of
Common Stock of the Company at an exercise price of $3.00 per share;

     WHEREAS, the Executive is currently serving as President and Chief
Executive Officer and a director of the Company;

     NOW, THEREFORE, in consideration of the undertakings and commitments
contained herein and other good and valuable consideration, the sufficiency of
which is acknowledged, the parties agree as follows:

        1.  Resignation. Effective as of July 31, 1998 (the "Commencement Date")
            -----------
     and except as provided in Sections 2 and 3 below, the Executive hereby
     resigns as President and Chief Executive Officer of the Company and from
     all other positions held with the Company and the Company's current
     subsidiaries (individually and collectively, the "Prodigy Entities"),
     including without limitation as a Trustee of The Prodigy Trust. The Company
     hereby accepts such resignations.

        2. Service as a Director. The Executive shall continue to serve as a
           ---------------------
     director of the Company and agrees to serve as a director until his death,
     resignation or removal in accordance with applicable law and the respective
     Certificates of Incorporation and by-laws of the Company. The Executive
     shall not be eligible to participate in any compensation arrangements put
     in place for outside directors so long as Consulting Period is in effect
     other than to be covered under the Company's standard directors liability
     insurance policy and to have reasonable expenses reallocated.

        3. Consulting Agreement. The Company desires to enter into a Consulting
           --------------------
     Agreement (the "Agreement"), effective as of the 1st day of August 1998,
     with Russell I. Pillar, presently residing at 174 West 76th Street, #12-H,
     New York, N.Y. (the "Consultant").

          3.1  Agreement.  The Company desires to retain the Consultant, and the
               ---------
          Consultant desires to be retained by the Company, as a consultant with
          respect to the matters described herein.  In consideration of the
          mutual covenants and promises contained herein, and other good and
          valuable consideration, the receipt 
<PAGE>

          and sufficiency of which are hereby acknowledged by the parties
          hereto, the parties agree as follows:
 
          3.2. Term of Engagement. The Company hereby agrees to retain the
               ------------------
          Consultant, and the Consultant hereby agrees to be retained by the
          Company, upon the terms set forth in this Agreement, for the period
          commencing on August 1, 1998, and ending on July 31, 1999 (the
          "Consulting Period"). The Agreement will be non-cancelable by the
          Company and will renew year-to-year unless either party terminates
          with 30 days advance notice prior the end of the then current year.

          3.3. Title; Capacity. The parties agree that the Consultant shall
               ---------------
          serve as Vice Chairman (a non-executive Board of Directors position),
          and will have responsibility for continuing to support the Chairman in
          setting corporate strategy, building and maintaining senior level
          relationships throughout the industry; speaking on behalf of the
          Corporation in public venues when appropriate; and continuing to help
          guide the Company to and through an initial public offering.

          3.4. Time Commitment. During the term, Consultant will be available
               ---------------
          from time-to-time on reasonable notice to consult with the Chairman,
          but in no case will Consultant be required to dedicate such time as
          would interfere with Consultant's ability to enter into full-time
          employment elsewhere or more than ten hours per month on a non-
          cumulative basis.

        4.  Fees and Expenses.
            -----------------

          4.1 Fees. In full compensation for services rendered under this
              ---- 
          Agreement, the Company shall pay the Consultant a fee of $250,000,
          payable in twelve (12) equal monthly installments, in advance on the
          first day of each month during the Consulting Period, with an initial
          payment of $20,833.33 payable upon execution of this Agreement.

          4.2 Performance Bonus. A performance bonus of $125,000 based on a
              -----------------
          successful initial public offering, payable in full 30 days after the
          IPO; otherwise discretionary based on performance and payable in
          February, 1999.

          4.3 Expenses. The Company shall reimburse the Consultant for all
              --------
          reasonable travel and other business expenses incurred or paid by the
          Consultant in connection with the performance of his duties hereunder,
          upon presentation by the Consultant of documentation, expense
          statements, vouchers and/or such other supporting information as the
          Company may reasonably request, provided, however, that the nature and
                                          --------  -------
          amount of such expenses shall be subject to the Company's expense
          policies as in effect from time to time.

<PAGE>

          4.4 Independent Contractor Status. The Consultant shall perform all
              -----------------------------
          services under this Agreement as an "independent contractor" and not
          as an employee or agent of the Company. The Consultant is not
          authorized to assume or create any obligation or responsibility
          express or implied, on behalf of, or in the name of, the Company or to
          bind the Company in any manner. The Consultant shall not be entitled
          to any benefits, coverages or privileges, including without limitation
          social security, unemployment, pension payments, made available to
          employees of the Company with respect to his services as a consultant.
          The Company shall not make any tax withholding with respect to the
          fees paid hereunder, and the Consultant shall be solely responsible
          for all income or other taxes attributable thereto. The parties agree,
          however, that the Executive's termination of employment on July 31,
          1998, shall constitute a qualifying event pursuant to the Consolidated
          Budget Reconciliation Act of 1985 (COBRA), and the Company shall
          afford the Consultant benefit continuation to the extent required by
          law at the Company's expense.

          4.5 Relocation. If the Consultant chooses to relocate out of the New
              ----------
          York City area any time during the term of this Agreement, the Company
          will pay all reasonable actual expenses incurred to relocate the
          Consultant, his family, automobile, and household goods to another
          city in the United States. In addition, the Company will pay any
          continuation of rent on the Consultant's apartment in New York City if
          the Consultant is unable to break the current lease without any
          payment, as well as applicable lease cancellation penalties.

          4.6 Administrative Support. The Consultant will continue to be
              ----------------------
          provided with his current office and full time assistant, Stacey
          Lettis, during the term of the consulting period. The Consultant will
          also be provided with a complimentary Prodigy Internet account for as
          long as he is a member of the Board of Directors.

          4.7 Company match of 401(k). The Company hereby waives existing
              -----------------------
          vesting restrictions on the Consultant's vesting schedule of the
          Company match of the Consultant's 401(k), and vests those amounts
          immediately upon signing of this Agreement.

        5.  Options.

        a.) On September 29, 1997, the Parent granted the Executive a stock
        option to purchase 625,000 shares of common stock of the Parent at an
        exercise price of $3.00 per share. Such options vest as follows:

          - 100,000 vested as of September 29, 1997;
          - 175,000 options shall vest on September 29, 1998;
          - 175,000 options shall vest on September 29, 1999;
          - 175,000 options shall vest on September 29, 2000 provided, however,
          that 75,000 of the shares which would otherwise vest on September 29,
          2000 (the "Performance Options"), shall vest upon the closing of an
          initial public offering by the Company by August 1, 1999. The parties
          agree that the vesting schedule specified in this Section 5 shall
          remain in effect and the options will continue to vest in the event
          that the Consulting Agreement is not renewed beyond July 31, 1999.
          Further, the Consultant may exercise a portion of or all his vested
          options for up to a period of 12 months after ceasing to be 

<PAGE>

        a member of the Board of Directors or a Consultant or 12 months from the
        final vesting date, if later, except that the Consultant shall have up
        until December 31, 2000 to exercise any or all shares under option
        except for those which vest on September 29, 2000, for which the
        Consultant shall have until September 28, 2001 to exercise. The parties
        acknowledge that the exercise price of all stock options referred to in
        this Section 5 has been reduced to $1.00 per share.

        b.) The Consultant, if requested by the Parent and the managing
        underwriter of the initial public offering of the Parent's securities
        (the "IPO"), agrees not to sell publicly or otherwise transfer or
        dispose of any securities of the Parent held by the Consultant for a
        specified period of time (not to exceed 180 days) following the
        effective date of the registration statement for the IPO; provided that
        all then executive officers, directors and holders of 5% or more of the
        outstanding stock of the Parent enter into similar agreements. The
        Consultant acknowledges that no representations have been made to him
        concerning the size, valuation or timing of any IPO.
 
        c.) All options and any additional shares owned by the Consultant will
        be registered by the Company (under an S-8 or other appropriate filing),
        at the time of the IPO filing.

        d.) Acceleration of Vesting Schedule. If there is a change of control of
            --------------------------------
        the Parent, pursuant to which one single person or entity has control of
        the Parent (as control is understood under the Internal Revenue Code or
        securities laws of the US), the vesting schedule on all options
        previously granted to the Consultant will be accelerated so that a total
        of 50% of the Consultant's unvested options selected from those options
        last scheduled to vest will be vested on the effective date of such
        merger or acquisition. The vesting schedule shall thereafter remain the
        same so that the remaining shares vest without giving effect to the
        shares, which vested on an accelerated basis.

        6. No Other Payments or Benefits. The parties acknowledge and agree that
           -----------------------------
     the payments, benefits and options described in Sections 4 and 5 above
     represent the sole and entire amounts or compensation due or to become due
     to the Consultant in connection with his services, his status and/or any
     and all other associations with the Prodigy Entities (including, without
     limitation, any termination of any of the forgoing or for any other reason
     whatsoever), and no further or other compensation including, without
     limitation, stock or other equity compensation, payments, bonuses,
     benefits, unused accrued vacation time, any and all other accrued but
     unpaid compensation, severance pay or other amounts whatsoever are or shall
     become due or payable at any time by the Prodigy Entities (or by any
     officer, director, employee or stockholder of the Prodigy Entities) to the
     Consultant other than customary expense reimbursements.

        7.  Proprietary Information and Developments.
            ----------------------------------------

        7.1  Proprietary Information.
             -----------------------

             (a) The Consultant agrees that all information and know-how,
             whether or not in writing, of a private, secret or confidential
             nature concerning the Company's business or financial affairs,

<PAGE>

             other than that which the Consultant learns and uses under the
             auspices of Critical Mass or a Critical Mass portfolio company
             (collectively "Proprietary Information") is and shall be the
             exclusive property of the Company. By way of illustration, but not
             limitation, Proprietary Information may include inventions,
             products, processes, methods, techniques, formulas, compositions,
             compounds, projects, developments, plans, research data, clinical
             data, financial data, personnel data, computer programs, and
             customer and supplier lists. The Consultant will not disclose any
             Proprietary Information to others outside the Company or use the
             same for any unauthorized purposes without written approval by the
             Chairman of the Parent, unless and until such Proprietary
             Information has become public knowledge without fault by the
             Consultant.

             (b) The Consultant agrees that all files, letters, memoranda,
             reports, records, data, sketches, drawings, laboratory notebooks,
             program listings, or other written, photographic, or other tangible
             material containing Proprietary Information, whether created by the
             Consultant or others, which shall come into his custody or
             possession, shall be and are the exclusive property of the Company
             to be used by the Consultant only in the performance of his
             services for the Company.

             (c) The Consultant agrees that his obligation not to disclose or
             use information, know-how and records of the types set forth in
             paragraphs (a) and (b) above, also extends to such types of
             information, know-how, records and tangible property of customers
             of the Company or suppliers to the Company or other third parties
             who may have disclosed or entrusted the same to the Company or to
             the Consultant in the course of the Company's business.

          7.2  Developments.
               ------------

             (a) The Consultant will make full and prompt disclosure to the
             Company of all inventions, improvements, discoveries, methods,
             developments, software, and works of authorship, whether patentable
             or not, which are created, made, conceived or reduced to practice
             by the Consultant or under his direction or jointly with others
             during his employment by the Company, whether or not during normal
             working hours or on the premises of the Company other than that
             which the Consultant created under the auspices of Critical Mass or
             a Critical Mass portfolio company (all of which are collectively
             referred to in this Agreement as "Developments").

             (b) The Consultant agrees to assign and does hereby assign to the
             Company (or any person or entity designated by the Company), all
             his right, title and interest in and to all Developments and all
             related patents, patent applications, copyrights and copyright
             applications.
 
             (c) The Consultant agrees to cooperate fully with the Company, with
             respect to the procurement, maintenance and enforcement of
             copyrights and patents (both in the United States and foreign
             countries), relating to 


<PAGE>

             Developments at no cost to the Company. Consultant shall sign all
             papers, including, without limitation, copyright applications,
             patent applications, declarations, oaths, formal assignments,
             assignment of priority rights, and powers of attorney, which the
             Company may deem necessary or desirable in order to protect its
             rights and interests in any Development.

          7.3  Other Agreements.  The Consultant hereby represents that his
               ----------------
          performance of all the terms of this Agreement and as a consultant to
          the Company does not and will not breach the terms of any agreement
          with any previous employer or other party to refrain from using or
          disclosing any trade secret, confidential or proprietary information,
          knowledge or data acquired by him in confidence or in trust prior to
          the consulting period or to refrain from competing, directly or
          indirectly, with the business of such previous employer or any other
          party.

          7.4  Entities Covered.  All references in this Section 7 to the
               ----------------
          "Company" shall include all Prodigy Entities.

          7.5  Effective Date.  The parties intend and agree that the provisions
               --------------
          of this Section 7 are intended to be, and shall be, effective as of
          September 29, 1997 (the date on which the Executive commenced
          employment with the Company).

        8.  Releases.
            --------

          8.1  By the Consultant.
               -----------------
 
             (a) In exchange for the payments and undertakings described within
             this Agreement and other good and valuable consideration, the
             receipt and sufficiency of which are hereby acknowledged, the
             Consultant, on behalf of himself and his representatives, agents,
             estate, heirs, successors and assigns, hereby absolutely and
             unconditionally releases and forever discharges the Prodigy
             Entities and/or their respective successors, assigns, stockholders,
             officers, directors, investors, employees, attorneys,
             representatives and agents, both individually and in their official
             capacities, from any and all actions or causes of action, suits,
             claims, complaints, contracts, liabilities, agreements, promises,
             debts, judgments, damages and demands of every kind or nature
             whether existing or contingent, known or unknown, both in law and
             equity, including without imitation: claims arising from or as a
             consequence of any actions or inactions of the directors or
             officers of the Prodigy Entities; any other contract, express or
             implied; and common law.

             (b) This release is intended by the Consultant to be all
             encompassing and to act as a full and total release of any claims
             that the Consultant has, may have or has had against the Prodigy
             Entities and their respective successors, assigns, directors,
             stockholders, officers, investors, employees, attorneys,
             representatives and/or agents, both individually and in their

                                       6
<PAGE>

             official capacity with the Prodigy Entities, since the beginning of
             the world through the date of this Agreement, specifically
             including, but without limitation to: any federal or state law or
             regulation dealing with either employment or employment
             discrimination; the Age Discrimination in Employment Act; the fair
             employment practices statute of any applicable jurisdiction; all
             claims arising from or in conjunction with the Consultant's
             employment and/or status as an officer of the Prodigy Entities; and
             all claims for compensation (such as: severance payments; benefits;
             accrued vacation pay; sick pay; reimbursable expenses; expense
             vouchers; obligations or commitments to grant stock options or to
             issue stock and all other rights to acquire stock, if any such
             obligations, commitments and/or rights are claimed to exist;
             performance or other bonuses; business-related expenses; and all
             other payments, commissions, compensations or reimbursements of
             every kind and description) other than the compensation expressly
             provided for in this Agreement.

             (c) The Consultant specifically waives any right he has or may have
             under applicable law to revoke this Agreement after its execution.
             The Consultant acknowledges that he was advised by the Company of
             his right to obtain independent legal advice regarding this
             agreement; that he has had the opportunity to review and reflect on
             all the terms of this Agreement; and that he has not been subject
             to any undue or improper influence interfering with the exercise of
             his free will to execute this Agreement.

          8.2  By the Prodigy Entities.  In exchange for the releases set forth
          above and other good and valuable consideration, the receipt and
          sufficiency of which are hereby acknowledge, the Company, on behalf of
          itself, the Prodigy Entities and their respective successors, assigns,
          directors, officers, employees, representatives and agents, hereby
          absolutely and unconditionally releases and forever discharges the
          Consultant, his representatives, agents, estate, heirs, successors and
          assigns, from any and all actions or causes of action, suits, claims,
          complaints, contracts, liabilities, agreements, promises, debts,
          judgments, damages and demands of every kind or nature whether
          existing or contingent, known or unknown, both in law and equity,
          including without limitation: claims arising from or as a consequence
          of the Consultant's acts or omissions as an officer or as a director
          of the Company; any other contract, express or implied; and common
          law. This release is intended by the Prodigy Entities to be all
          encompassing and to act as a full and total release of any claims that
          any Prodigy Entities has, may have or has had against the Consultant
          or his representatives, agents, estate, heirs, successors and assigns,
          since the beginning of the world through the date of this Agreement.

          8.3  Exceptions.  The foregoing release shall not apply to any act or
               ----------
          omissions of either party occurring after the date hereof relating to
          any breach of this Agreement and the Employment Agreement of September
          29, 1997 is terminated effective July 31, 1998.

                                       7
<PAGE>
 
          8.4  No Admissions.  Nothing in this Agreement is to be construed as
               -------------
          an admission or acknowledgment by the Prodigy Entities and/or their
          respective stockholders, officers, directors, investors, employees,
          representatives or agents, of any unlawful, wrongful or negligent
          conduct or as an admission or acknowledgment of any liability
          whatsoever.  Nothing in this Agreement is to be construed as an
          admission or acknowledgment by the Consultant of any unlawful,
          wrongful or negligent conduct or as an admission or acknowledgment of
          any liability whatsoever.

          8.5  Continuing Rights to Indemnification.  It is expressly agreed and
               ------------------------------------
          understood that nothing in this Agreement shall affect the parties'
          rights and obligations relating to indemnification pursuant to the
          Certificate of Incorporation of the Company, bylaws, Employment
          Agreement, or law.

        9. Confidentiality. The parties agree that the terms and contents of
           ---------------
     this Agreement, the contents of the negotiations and discussions resulting
     in this Agreement, shall be maintained as confidential by the parties,
     their agents and representatives, and none of the above shall be disclosed
     except by either party for the purpose of enforcing this Agreement, to the
     extent required by federal or state law, to the extent otherwise provided
     for in this Agreement, or as agreed to in writing by the authorized agents
     of each party.

        10. Notices and Payments. All notices, payments and communications shall
            --------------------
     be given or made to the parties by hand delivery or first class prepaid
     mail at the following addresses, or such other addresses as the parties
     shall inform each other of in writing as aforesaid:

     If to the Consultant:    Russell I. Pillar
                              174 West 76th Street, #12-H
                              New York, NY 10023

     If to the Company:       Prodigy, Inc.
                              44 So. Broadway
                              White Plains, NY 10601
                              Attention:  General Counsel

        11. No Other Inducement. In entering into this Agreement, neither party
            -------------------
     has relied on any representation, promise or inducement made by the other
     party, except as expressly provided herein.

        12.  Entire Agreement.  This Agreement constitutes the sole and entire
             ----------------
     agreement between the parties as to its subject matter and supersedes and
     terminates any and all other agreements, understandings and representations
     as to its subject matter, and the parties acknowledge and agree that there
     are no other agreements, understandings and/or representations of any kind
     whatsoever remaining between them except as set forth herein.

                                       8
<PAGE>

        13.  Miscellaneous.
             -------------  

          13.1  The descriptive section headings herein have been inserted for
          convenience only and shall not be deemed to limit or otherwise affect
          the construction of any provision hereof.  There shall be no
          presumption that ambiguities, if any, in this Agreement shall be
          construed for or against either party.

          13.2  This Agreement shall be construed, interpreted and enforced in
          accordance with the laws of the State of New York, without reference
          to conflict of laws principles.

          13.3  This Agreement shall not be assignable by the Consultant or by  
          the Company but, except to the foregoing extent, shall be binding on
          the parties hereto and their respective heirs, legal representatives,
          successors and assigns and shall inure to the benefit of the Company's
          successors and assigns. This Agreement may be modified or amended and
          any provision hereunder waiver only by written agreement signed by the
          parties.

          13.4  The parties agree that each provision herein shall be treated as
          a separate and independent clause, and the unenforceability of any one
          clause shall in no way impair the enforceability of any of the other
          clauses herein. Moreover, if one or more of the provisions contained
          in this Agreement shall for any reason be held to be excessively broad
          as to scope, activity or subject matter so as to be unenforceable at
          law, such provision or provisions shall be construed by limited and
          reducing it or them, so as to be enforceable to the extent compatible
          with the applicable law as it shall then appear.

          13.5  This Agreement may be executed in any number of counterparts,
          each of which shall constitute an original, but which taken together
          shall constitute one instrument.
 
          IN WITNESS WHEREOF, this Agreement is entered into under seal by the
Company and the Consultant as of the date set forth above.

                     /s/  Russell Pillar
                    ---------------------------------  
                               Russell I. Pillar

                    PRODIGY SERVICES CORPORATION


                    By:  /s/   Samer Salameh
                       ---------------------------------  
                                  Samer Salameh
                                     Chairman

                                       9
<PAGE>
 
                                AMENDMENT NO. 1
                                       TO
                                   AGREEMENT


          THIS AMENDMENT NO. 1, (the "Amendment") dated this 5th day of January,
1999, to the Agreement dated as of August 1, 1998 (the "Agreement") between
Prodigy Communications Corporation (the "Company") with its principal place of
business at 44 South Broadway, White Plains, New York and Russell I. Pillar,
residing at 174 West 76th Street, #12, New York, New York  (the "Consultant").

          Whereas, the Company and the Executive are parties to the Agreement,
pursuant to which Executive agreed to perform certain consulting services for
the Company and to serve as Vice Chairman of its Board of Directors; and

          Whereas, the parties desire to amend the Agreement as provided herein;

          NOW THEREFORE, for good and valuable consideration, the receipt and
sufficiency of which are hereby acknowledged, the parties hereby agree, and the
Agreement is hereby amended, as follows:

        1.  Termination of Consulting Services. The parties agree that effective
            ----------------------------------
            as of the date hereof, the Consultant shall no longer provide
            consulting services for the Company, and the provisions specified in
            Article 3 of the Agreement shall be of no further force or effect.

        2.  Service As Director. Notwithstanding termination of the consulting
            -------------------
            services, Consultant hereby resigns his position as Vice Chairman of
            the Company, but agrees to continue to serve as a director of the
            Company until resignation or removal in accordance with applicable
            law and the Certificate of Incorporation and bylaws of the Company.
            In consideration of the compensation arrangements described herein,
            Consultant agrees that he shall not be eligible for additional
            compensation as a director until such time as the Company adopts
            compensation arrangements for outside directors (at which time he
            will participate in such compensation arrangements), except that
            Consultant shall be entitled to reimbursement for reasonable out of
            pocket travel expenses relating to attendance at Board meetings, in
            accordance with Company policy.

        3.  Compensation. In lieu of the compensation and all other arrangements
            -------------
            specified in Article 4 of the Agreement, and as full consideration
            for the early termination of the Consulting Services and ongoing
            service as a member of the Board of Directors of the Company, the
            Company shall pay to Consultant a fee of $145,833.31, such fee to be
            paid to Consultant upon 

<PAGE>
 
            execution of this Amendment. Additionally, in lieu of any bonus
            stated in the Agreement on completion of the initial public offering
            of the Company's stock, Company shall pay to Consultant a
            discretionary bonus based upon performance of $106,250, such amount
            to be payable on execution of this Agreement.

        4.  Options. The options to purchase 625,000 shares of common stock of
            -------
            the Company specified in Article 5 of the Agreement, and the vesting
            schedule, lock up provisions, registration rights and acceleration
            events specified therein shall continue in effect as specified
            therein.

     Except as expressly provided herein, the Agreement shall remain in full
force and effect, and the parties agree to be bound by the terms thereof, as
amended herein.

 
                                Prodigy Communications Corporation



                                By: /s/ Samer Salameh
                                   ---------------------------
                                   Samer Salameh
                                   Chief Executive Officer


 
                                By: /s/ Russell I. Pillar
                                   ---------------------------
                                    Russell I. Pillar