<PAGE>
 
                                                                   EXHIBIT 10.24

                             CONSULTING AGREEMENT

          Consulting Agreement dated June 1, 1995, between United International
Holdings, Inc., a Delaware corporation, (the "Company") and Mark L. Schneider
("Consultant") who resides in Arapahoe County, Colorado.

                                    Recitals

          Consultant has resigned as president of the Company and has agreed to
serve as a consultant to the Company on the terms of this Agreement.  He will
continue to serve as a director. This Agreement is intended to describe the
entire relationship between Consultant and the Company with respect to his
former employment, his future consulting services to the Company and his
services as the Company's representative with other entities.

          Consultant has significant experience in international cable
television franchise development, television programming and related businesses,
and the Company intends to call upon that experience as it considers advisable
in its absolute discretion in connection with its international cable television
business.


                                   Agreement

          For good and valuable consideration, the receipt and sufficiency of
which are acknowledged, the Company and Consultant agree as follows.
<PAGE>
 
          1.   Term.  The Company agrees to retain Consultant and Consultant
               ----                                                         
agrees to serve the Company for a period beginning on the date of this Agreement
and ending on May 31, 2000 (the "Consulting Period").

          2.   Duties; Supervision.  For up to 90 days, including travel days,
               -------------------                                            
each calendar year, Consultant will provide consulting services to the Company
only as assigned by the Chief Executive Officer of the Company or such other
officer of the Company as the Board of Directors shall from time-to-time
designate as the officer responsible for the supervision of Consultant's
services hereunder ("Executive Officer"). Consultant's services shall be
scheduled to accommodate Consultant's other business activities to the extent
reasonably possible.  Consultant shall report to the Executive Officer with
respect to Consultant's services hereunder and shall be subject to the Executive
Officer's sole supervision.  Consultant's assignments will be made by the Chief
Executive Officer, will be commensurate in status to the services provided by
Consultant as President of the Company and, it is anticipated, will relate to
technology, telephony and programming services and franchise business, new
business in foreign countries, and acting as the Company's liaison with, and as
a board member of, Interactive Television Network.  The Executive Officer shall
provide reports of Consultant's services hereunder to the Chairman of the Board
of Directors of the Company (the "Chairman") from time to time and, as
requested, to the Board of Directors or to the committee of the Board described
in Section 12.

                                      -2-
<PAGE>
 
          3.   Compensation; Reimbursements.  (a) Cash,  Benefits.  The Company
               ----------------------------       ------ --------              
shall pay Consultant an annual fee of $300,000 during the Consulting Period in
equal semi-monthly installments on its normal payroll days.  Consultant shall be
entitled to health and dental insurance, disability insurance and similar
benefits that are provided to executive officers of the Company, and shall have
all other incidental perquisites available to Consultant in his previous
capacity as President of the Company or made available to the top executives of
the Company.  The Company shall not, however, be required to adopt or to
maintain in existence any benefit plan or modify the terms of eligibility under
any plan to accommodate Consultant, but shall, if Consultant is ineligible under
any such plan, provide comparable benefits purchased separately.

               (b) Office Expenses.  The Company shall pay or shall reimburse
                   ---------------                                           
Consultant for reasonable office expenses incurred by him during the Consulting
Period, including actual rent incurred for up to 1,500 square feet of office
space plus parking for Consultant and a secretary, salary of a secretary,
expenses for office equipment and supplies, accounting services, and startup
costs for establishing an office in a Class A building outside the Company's
offices, such that Consultant will have an office and working space for a
secretary and other functions equivalent to the office space provided to
Consultant by the Company during his tenure as President.

                                      -3-
<PAGE>
 
               (c) Stock Options. All options to purchase stock in the Company
                   -------------
that are held by Consultant as of the date of this Agreement and that are not
vested shall vest on the date of this Agreement. All unexercised options held by
Consultant shall expire in accordance with the applicable plan or agreement
governing such options. Consultant shall be entitled to receive additional
options to acquire stock of the Company during the Consulting Period in an
amount to be determined by the Board of Directors on the recommendation of the
Chairman, but shall receive at least options to purchase a number of shares of
the Company equal to 90 per cent of the average number of shares provided in
options granted to the Chairman, Chief Executive Officer, Chief Operating
Officer, Chief Financial Officer and Executive Vice President. The calculation
of such shares shall be equitably adjusted for unusual circumstances including,
without limitation, (i) any initial extraordinary grant to a newly hired officer
to fill a vacancy in any of those positions shall be excluded from the
calculation, but subsequent grants in the ordinary course to such new officer
shall be included, and (ii) if any such office is not filled and option grants
are not made with respect to such position, appropriate adjustments shall be
made to reflect that circumstance in determining the average number of options
granted, the intent being that, over the term of this Agreement, Consultant
shall receive options to purchase a number of shares not less than 90 percent of
the number of shares in options granted to the top five officers of the Company.
Any such options granted during the Consulting Period shall be at prices
(including any favorable repricing), and with vesting

                                      -4-
<PAGE>
 
provisions and other terms (to the extent permitted under applicable law)
substantially equivalent (but no less favorable) to those granted to the other
executive officers of the Company. To the extent that other compensation
programs for the executives listed above are instituted in lieu of stock
options, Consultant shall participate in those programs such that the change in
the form of compensation to such executives is not detrimental to his rights
under this Paragraph 3(c).

          (d) Expenses.  The Company shall pay directly or reimburse Consultant
              --------                                                         
for the reasonable amount of hotel, travel, entertainment and other expenses
necessarily incurred by Consultant in the discharge of his duties hereunder upon
submission and approval of written statements and bills in accordance with the
then regular procedures and standards of the Company for reimbursement of
expenses incurred by the Chairman and the Chief Executive Officer of the
Company.

          (e) No Director's Fees.  During the Consulting Period, Consultant will
              ------------------                                                
not be separately compensated for his services as a director of the Company, and
will be entitled to reimbursement of expenses incurred in performing his duties
as a director on the same basis as employees of the Company are reimbursed for
expenses they incur as a director of the Company.

          (f) Attorney' Fees.  The Company shall reimburse Consultant for the
              --------------                                                 
reasonable fees and expenses of his attorneys 

                                      -5-
<PAGE>
 
incurred in connection with the preparation of this Agreement and related 
matters.

          4.   Termination.  If during the Consulting Period
               -----------                                  

               (a)  either

                    (i)(A) the Board of Directors of the Company shall determine
that it is desirable to terminate this Agreement or (B) the Company shall breach
any material term of this Agreement and, if such breach is curable, shall fail
to correct such breach within 20 days after notice by Consultant to the Company
of its commission of the same; or

                    (ii)(A) Consultant shall be convicted by a final, non-
appealable judgment of a felony involving moral turpitude, or (B) Consultant
shall desire to terminate this Agreement other than pursuant to Subparagraph
4(a)(i)(B) above, then, and in each such case, either the Company or the
Consultant (whichever is applicable) shall have the right to give notice of
termination of Consultant's services hereunder. This Agreement and Consultant's
services hereunder shall terminate on the date specified in such notice, which
shall not be sooner than 10 days after the date such notice is given (except in
the case of a termination pursuant to Subparagraph 4(a)(i)(B) or Subparagraphs
4(a)(ii)(A) or (B), which may be effective immediately).

                                      -6-
<PAGE>
 
          (b) If Consultant shall die during the Consulting Period, then this
Agreement shall terminate on the date of Consultant's death.

          (c) In the case of a termination pursuant to Subparagraph 4(a)(ii),
Consultant shall be entitled to receive his compensation benefits and
reimbursements at the rates and at the times provided in Section 3 only to the
date on which such termination shall take effect and shall thereafter be
entitled to no further compensation, benefits or reimbursements under this
Agreement.  The termination of this Agreement shall not, of itself, affect any
benefit otherwise available to Consultant from the Company in accordance with
its terms after termination of employment.

          (d) In the case of a termination pursuant to Subparagraph 4(a)(i) or
Paragraph 4(b), (i) Consultant or his personal representative shall be entitled
to receive Consultant's compensation, including all benefits and payments under
Paragraphs 3(a), 3(b) and 3(c), after the date of termination at the rate and at
the times provided in Section 3 to the end of the Consulting Period (except in
the case of termination pursuant to Paragraph 4(b) options to which Consultant
would be entitled under Paragraph 3(c) shall be granted in the calendar year of
death in proportion to the number of months (or part thereof) elapsed in the
year, and none shall be granted thereafter), (ii) all stock options held by
Consultant that are not vested as of the date of such termination shall
immediately vest, and (iii) 

                                      -7-
<PAGE>
 
all stock options held by Consultant shall expire in accordance with the
applicable plan, if any, or stock option agreement governing such options;
provided Consultant shall receive reimbursement for expenses pursuant to
Paragraph 3(d) only for expenses incurred through the date of termination.

          5.   Noncompetition and Noninterference.  (a)  In view of the unique
               ----------------------------------                             
and important services that Consultant has been retained to render to the
Company, Consultant's knowledge of proprietary information relating to the
business of the Company, and entities in which it owns, directly or indirectly,
an equity interest ("Related Companies"), and similar knowledge regarding the
Company and Related Companies that Consultant currently has and that it is
expected that Consultant will obtain, and in consideration of the compensation
to be received hereunder, Consultant agrees, subject to Paragraph 5(b), that
during the Consulting Period, he will not without the consent of the Company
Participate In (as hereinafter defined in this Paragraph 5(a)) any business that
competes with the Company or any Related Company in any material respect in the
subscription television, telephony and related business in the respective
specific geographic areas in which the Company or such Related Company conducts
business.  For purposes of this Section 5, the term "Participate In" shall mean:
"directly or indirectly, for his own benefit or for, with or through any other
person, firm or corporation, own, manage, operate, control, or participate in
the ownership, or control of, or be connected with as a director, officer,
employee, partner."  Notwithstanding the foregoing, 

                                      -8-
<PAGE>
 
Consultant shall not be deemed to Participate In a business merely because he
owns not more than 5% of the outstanding common stock of a corporation, if, at
the time of its acquisition by Consultant, such stock is listed on a national
securities exchange, is reported on Nasdaq or is regularly traded in the over-
the-counter market by a member of a national securities exchange. Consultant
also agrees that until the earliest of (i) one year after the termination of
this Agreement pursuant to Subparagraph 4(a)(ii)(B), and (ii) the expiration of
the Consulting Period or earlier termination of this Agreement pursuant to
Subparagraph 4(a)(i), he will not (i) Participate In any business or
organization (a "Competitor") in a capacity that directly assists such
Competitor in competing with the Company or any Related Company in any material
respect in the subscription television, telephony and related businesses in the
respective specific geographic areas where the Company or any Related Company
conducted such businesses at the time this Agreement terminated, (ii) own a
controlling interest in a business or organization that competes in a material
respect in the subscription television, telephony and related businesses in the
respective specific geographic areas where the Company or any Related Company
conducted such businesses at the time this Agreement terminated, or (iii)
solicit or interfere with, or endeavor to entice away from the Company or any
Related Company, any of their respective employees, consultants or partners. The
employment by Consultant or a business that Consultant Participates In of a
person employed or formerly employed by the Company shall not be prohibited by
this Paragraph if such person 

                                      -9-
<PAGE>
 
sought out such employment on his own initiative. Consultant agrees that the
provisions of this Section 5 are necessary and reasonable to protect the Company
and each Related Company in the conduct of their respective businesses. If any
restriction contained in this Section 5 shall be deemed to be invalid, illegal
or unenforceable by reason of the extent, duration or geographical scope hereof,
or otherwise, then the court making such determination shall have the right to
reduce such extent, duration, geographical scope or other provisions hereof, and
in its reduced form such restriction shall then be enforceable in the manner
contemplated hereby.

               (b) Notwithstanding Paragraph 5(a), Consultant shall not be
limited in his ability to Participate In or otherwise conduct any business or
pursue any business opportunity specifically declined by the Company that
Consultant has first offered to the Company on terms substantially equivalent to
the terms on which Consultant has the opportunity to participate individually or
with others and as to which Consultant has provided the Company with all
information available to him. If the Company does not accept Consultant's offer
within 20 business days and thereafter diligently and in good faith pursue the
negotiation of a definitive agreement as to its participation in such business
or business opportunity, the matter will be deemed to have been declined.

          6.   Confidentiality.  Consultant agrees that during the Consulting
               ---------------                                               
Period (otherwise than in the performance of his 

                                      -10-
<PAGE>
 
duties hereunder) and thereafter, he shall use his reasonable efforts to prevent
the public disclosure of any confidential or proprietary information concerning
the business, accounts or finances of the Company or any Related Company that
have come to his knowledge during his employment with the Company or any of it
Related Company, and which have not previously been publicly disclosed.

          7.   Delivery of Materials.  Consultant agrees that at the request of
               ---------------------                                           
the Company upon the termination of the Consulting Period he will deliver to the
Company all documents, papers, materials and other property of the Company or
any Related Company relating to their affairs, which may then be in his
possession or under his control.  Consultant may, however, retain all
memorabilia and personal papers that have been acquired during the course of his
engagement.

          8.   Remedies.  (a)  Upon any material breach by Consultant of the
               --------                                                     
terms of this Agreement, the Company and any Related Company shall be entitled,
in addition to any other remedies available to it if it so elects, to institute
and prosecute proceedings at law or in equity to obtain damages with respect to
such breach or to enjoin Consultant from engaging in any activity in violation
hereof.  Consultant agrees that any breach or threatened breach by Consultant of
any of Sections 5, 6, or 7 hereof may cause immediate, irreparable injury to the
Company and any affected Related Company and that money damages may not provide
an adequate remedy for any such breach or threatened breach.  Accordingly,
Consultant hereby agrees that upon any such breach or 

                                      -11-
<PAGE>
 
threatened breach by him of such Sections the Company or any affected Related
Company shall be entitled, in addition to any other lawful remedies that may be
available to it, to seek injunctive relief.

               (b) The Company may, in addition to the remedies described in
Paragraph 8(a), sue for damages for breach of this Agreement by Consultant upon
authorization of its Board of Directors.

               (c) Consultant agrees that his sole and exclusive remedy for any
breach of this Agreement by the Company shall be the termination of this
Agreement and, upon such termination, the receipt by him of any amounts due him
hereunder as provided in Section 4.  Nothing contained in this Subparagraph 8(c)
shall limit Consultant's remedies for any act or omission of the Company, except
with respect to the Company's breach of this Agreement.

          9.   Indemnification.  The Company will indemnify and hold harmless
               ---------------                                               
Consultant in respect of any liability, damage, amount paid in settlement, cost
or expense (including reasonable counsel fees) incurred in connection with any
threatened, pending or completed claim, action, suit, proceeding or
investigation (whether civil, criminal or administrative) by any person other
than the Company to which he is or was a party, or threatened to be made a
party, by reason of his being or having been an 

                                      -12-
<PAGE>
 
officer, director, employee or consultant of the Company or serving at the
request of the Company as a director, officer, employee or agent of a Related
Company to the full extent permitted by the Certificate of Incorporation or
Bylaws of the Company, any standard indemnity agreement between the Company and
its officers and directors, or by applicable law.

          10.  Release by Consultant.  (a)  In consideration of the rights and
               ---------------------                                          
obligations created by this Agreement, Consultant for himself, his heirs,
personal representatives, successors and assigns, hereby fully and forever
releases and discharges the Company, its affiliates, Related Companies and each
of them, as well as their officers, directors, shareholders, employees, agents,
attorneys and the successors and assigns of each of them, from any and all
claims, demands, obligations, actions, liabilities and damages of every kind and
nature whatsoever, at law or in equity, known or unknown, suspected or
unsuspected, that Consultant may now have or claim at any future time to have,
based in whole or in part upon any act or omission through the date of this
Agreement, including without limitation those claims, demands, obligations,
actions, liabilities and damages arising from, relating to or based upon
Consultant's employment with the Company or separation from employment with the
Company, except as provided herein.

              (b) Consultant agrees that the release in Paragraph 10(a) includes
but is not limited to an express waiver of rights and claims under federal and
state statutes that

                                      -13-
<PAGE>
 
prohibit employment discrimination on the basis of sex, race, national origin,
religion, disability and age, as well as all common law rights and claims, such
as breach of contract, express or implied, tort, whether negligent or
intentional, constructive discharge, and wrongful discharge. Consultant agrees
that the benefits under this Agreement, which he accepts by signing this
Agreement and to which he would not otherwise be entitled to the extent provided
herein, have value to him that exceeds the value of compensation only for his
services as a consultant to the Company.

               (c) It is intended that this release be construed in the broadest
possible manner, to further the intention of the parties that all potential
disputes between them arising out of or connected to Consultant's employment
with the Company and any Related Company be forever resolved, subject only to
the exceptions in Paragraph 10(d) below.

               (d) Consultant's release in Paragraph 10(a) does not include (i)
the indemnity obligations described in Section 9 of this Agreement, (ii) any
indemnity obligations under any indemnity agreement between Consultant and the
Company or any Related Company, (iii) any reimbursement due Consultant as of the
date hereof for expenses that are reimbursable under current Company policies,
or (iv) claims arising after the date hereof.

          11.  Release by the Company.  (a) In consideration of the rights and
               ----------------------                                         
obligations created by this Agreement, the 

                                      -14-
<PAGE>
 
Company, for itself, as well as (to the extent that the Company may legally do
so) its officers, directors, shareholders, employees, agents, attorneys,
successors and assigns, hereby fully and forever releases and discharges
Consultant, his heirs, personal representatives, successors and assigns, from
any and all claims, demands, obligations, actions, liabilities and damages of
every kind and nature whatsoever, at law or in equity, known or unknown,
suspected or unsuspected that the Company may now have or claim at any future
time to have, based in whole or in part upon any act or omission through the
date of Consultant's separation from employment with the Company, including
without limitation those claims, demands, obligations, actions, liabilities and
damages arising from, relating to or based upon Consultant's employment with the
Company or separation from employment with the Company.

               (b) It is intended that this release be construed in the broadest
possible manner, to further the intention of the parties that all potential
disputes between them arising out of or connected to Consultant's employment
with the Company and any Related Company be forever resolved.

          12.  Dispute Resolution.  Any dispute or disagreement between
               ------------------                                      
Consultant and the Executive Officer arising under Sections 2, 13 or 14 of this
Agreement shall initially be referred to the Executive Officer and the Chairman
who shall meet together with Consultant in one or more meetings initiated at the
request of any of them.  If they are unable to resolve any 

                                      -15-
<PAGE>
 
dispute within a reasonable time, the dispute shall be referred at the request
of any of them to a committee of the Board of Directors to resolve such
disputes. The committee shall consist initially of the Chairman, Lawrence Flinn,
Jr. and Bruce Spector, or in his absence, Antony Ressler. If any of them shall
no longer be a member of the Board of Directors of the Company, the Board of
Directors shall select a replacement member of the committee. The decision of
the majority of the committee with respect to any dispute referred to them shall
be binding on Consultant and the Company, subject always to the authority of the
Board of Directors of the Company. No provision in Sections 2, 13 or 14 of this
Agreement and no decision of the committee or the Board of Directors may be the
basis for claim of breach of the Company's obligations hereunder.

          13.  Resignation from other Boards.  Consultant shall resign promptly
               -----------------------------                                   
from the boards of directors or other governing bodies of each Related Company
and as an officer of each of them upon request of the committee of the board of
directors of the Company described in Section 12 of this Agreement.  The
committee shall give due consideration to Consultant's duties hereunder as they
may relate to the offices held in Related Companies and to appropriate
transitions to other personnel; however, it may exercise its discretion
absolutely with respect to any such decision.  The decision of the majority of
the committee, however, shall be binding on Consultant and the Company as
provided in Paragraph 12 above.  No severance or other compensation shall be
payable to Consultant by virtue of his 

                                      -16-
<PAGE>
 
service with a Related Company or his resignation at the request of the
committee.

          14.  Publicity.  The Company and Consultant shall mutually agree upon
               ---------                                                       
a press release and a letter to employees of the Company and similar public
relations matters with respect to Consultant's resignation from the Company and
the terms of this Agreement.  Any dispute as to the content of any such release,
letter or other publicity shall be resolved by the Chairman and Executive
Officer, or, if they cannot agree, by the committee described in Section 12.
The Company may, however, make any release or securities law filing that its
counsel advises is necessary or advisable without Consultant's consent.

          15.  Survival.  The covenants, agreements, representations and
               --------                                                 
warranties contained in or made pursuant to this Agreement shall survive
termination of this Agreement as provided herein.

          16.  Notices.  All notices to be given hereunder shall be deemed duly
               -------                                                         
given when delivered personally in writing, sent by fax to the numbers provided
below, or five days after mailed, certified mail, return receipt requested,
postage prepaid and addressed as follows:

                                      -17-
<PAGE>
 
               If to be given to the Company:

                    United International Holdings, Inc.
                    4643 South Ulster Street
                    Suite 1300
                    Denver, Colorado 80237

                    Fax:  (303) 770-8464
                    Attn:  Chairman
                    and
                    Attn:  Chief Executive Officer

          If to be given to Consultant:

               Mark L. Schneider
               4828 South Albion Street
               Littleton, Colorado  80121

or to any such address or fax number as either of the parties may furnish to the
other in writing in accordance with this Section 16 except that notices of
change of address or fax number shall not be deemed given until received.

          17.  Miscellaneous.  This Agreement may not be amended nor may any
               -------------                                                
provision hereof be waived, except by an instrument in writing duly signed by
the party sought to be charged with such amendment or waiver, and constitutes
the entire agreement between the Company and Consultant with respect to the
subject matter hereof.  This Agreement shall be interpreted, governed and
controlled by the internal laws of the State of Colorado, without reference to
principles of conflict of laws.  In any proceeding under this Agreement, the
prevailing party shall be entitled to receive reasonable attorney's fees.

                                      -18-
<PAGE>
 
          18.  Approval.  This Agreement has been negotiated between Consultant
               --------                                                        
and disinterested members of the Board of Directors of the Company and was
approved by the disinterested members of the Board of Directors of the Company.

                         United International Holdings, Inc.



                         By:      /s/ Bruce H. Spector
                              ------------------------
                              Bruce H. Spector
                              Director

                         and



                         By:      /s/ Lawrence Flinn, Jr.
                              ---------------------------
                              Lawrence Flinn, Jr.
                              Director



                             /s/ Mark L. Schneider
                         -------------------------
                         Mark L. Schneider

                                      -19-