Sachverhalt: A. X._ (Klägerin, Beschwerdeführerin) war ab Januar 2000 bei A._ Ltd., London, als Executive Director in der Personalvermittlung angestellt. Sie gab diese Stelle bereits Ende Februar 2000 wieder auf. Im Februar und März 2000 führte sie Gespräche über eine Zusammenarbeit mit B._. Dieser war damals Managing Director und European Representative der C._ Group und - nachdem diese Investorengruppe zusammen mit Mitinvestoren 1999 den Y._ Konzern übernommen hatte - seit November 1999 Verwaltungsratspräsident der Y._ AG (Beklagte, Beschwerdegegnerin). Am 24. März 2000 verfasste B._ auf Briefpapier der C._ Group folgendes Schreiben an die Beschwerdeführerin: "Dear X._, Further to our conversations regarding the terms of your engagement as Assistant to the Chairman of Y._, I am pleased to propose the following terms. Position: Assistant to the Chairman of Y._ (the «Company»). Based in Brussels with offices in Brussels at the office of D._ and in London at the headquarters of the C._ Group Europe, Ltd. Sign-up Bonus: $ 50,000 Basic salary: $ 300,000, paid in 12 equal monthly installments. Basic Salary will be increased by 10 % annually. Annual Bonus: 50-150 % of Basic Salary, based upon performance. Share of value creation: - Option on .5% of the Company's shares («Options»), exercisable at a price per Company share equal to C._ Group's buy-in price per Company share. - Options vest on the following schedule: 20 % upon signing of a definitive agreement; 20 % upon 12 months continuous service; 20 % upon 24 months continuous service; 20 % upon 36 months continuous service; and 20 % upon 48 months continuous service. - Options will be granted by the Company under its incentive stock option plan for senior management and consultants. The number of options granted will be reviewed and may be increased after 24 months continuous service. Duration: The Agreement will be for a four-year term, with a start date of July 10, 2000. Part-time work before the start date will be compensated at a daily rate based on the Basic Salary. Miscellaneous: - Structure of agreement (e.g., consultancy or employment) to be mutually agreed. Payment entity to be determined. - Assistant to be based in London and right to hire a business analyst to be based in Brussels, London or Switzerland. - Three months paid maternity leave (to be counted for purposes of option vesting and bonus). - Insurances: Health, Dental, Life and Disability at substantially the same level of current coverage. - Four weeks of holidays. - Reimbursement annually for tax, accounting or estate planning expenses. - Reimbursement for work-related expenses, including child care and travel expenses as required. If you accept this offer, I will instruct Y._ management to prepare final documentation for your review immediately. In consultation with Y._'s Belgian and U.K. legal advisors, we will work together to structure your relationship with the company in the most efficient manner possible. I trust that you will share my enthusiasm over the opportunity to participate in Y._'s success, and I look forward to working with you. Sincerely, B._ Chairman of the Board, Y._ Acceptet and agreed to: X._" Die Beschwerdeführerin unterzeichnete diesen Brief und nahm in der Folge die darin beschriebene Teilzeittätigkeit auf. Die beidseits beigezogenen Anwälte arbeiteten mehrere detaillierte Vertragsentwürfe aus. B._ eröffnete der Beschwerdeführerin indes am 23. Juni 2000, dass er die Zusammenarbeit beenden wolle, was er am 7. Juli 2000 schriftlich bestätigte. B. B.a. Am 25. Juli 2000 erhob die Beschwerdeführerin beim Amtsgericht Olten-Gösgen Klage gegen die Y._ AG. An der Hauptverhandlung vor Amtsgericht am 30. August 2011 stellte sie folgende Rechtsbegehren: "1. Die Beklagte sei zu verpflichten, der Klägerin den Betrag von US$ 2'432'738.-- nebst Zins zu 5 % seit 1. Juli 2000 zu bezahlen; unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten. 2. Das Klagebegehren vom 25. Juli 2000 sei über den Teilbetrag von US$ 23'940.-- zufolge Gegenstandslosigkeit abzuschreiben; unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten. 3. Dies alles unter dem ausdrücklichen Vorbehalt des Nachklagerechts für die ausstehenden Optionsansprüche. 4. Auf die Widerklage gemäss Ziffer 2 des mit Klageantwort vom 31. August 2001 gestellten Begehrens sei nicht einzutreten, eventualiter sei die Widerklage abzuweisen; unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten." Die Beschwerdegegnerin beantragte: "1. Die Klage sei abzuweisen. 2. Es sei festzustellen, dass die Klägerin und Widerbeklagte keinerlei Ansprüche gegenüber der Beklagten und Widerklägerin oder irgendeiner anderen Y._-Konzerngesellschaft oder deren Beteiligte, Aktionäre und Organe hat. 3. Unter Kosten- und Entschädigungsfolgen zu Lasten der Klägerin und Widerbeklagten." Die Beschwerdeführerin machte mit ihrer Klage im Wesentlichen geltend, die Parteien hätten am 24. März 2000 einen Arbeitsvertrag mit einer festen Vertragsdauer von vier Jahren nach schweizerischem materiellem Recht abgeschlossen. Sie sei am 23. Juni 2000 grundlos fristlos entlassen worden. Die Beschwerdegegnerin bestritt in ihrer Klageantwort und Widerklage das Zustandekommen eines Arbeitsvertrags; der auf Wunsch der Klägerin verfasste Brief vom 24. März 2000 bestätige lediglich die bereits besprochenen Eckdaten des geplanten Vertrags, insbesondere den Lohn. Ohnehin sei auf den Sachverhalt belgisches Recht anwendbar. Das Amtsgericht Olten-Gösgen fällte am 30. August 2011 folgendes Urteil: "1. Die Beklagte hat der Klägerin folgende Beträge zu bezahlen: - US$ 4'698.-- nebst Zins zu 5 % seit 1. Juli 2000; - US$ 50'000.00 nebst Zins zu 5 % seit 10. Juli 2000; - US$ 450'000.-- nebst Zins zu 5 % seit 9. Januar 2001 (mittlerer Verfall 10. Juli 2000 - 9. Juli 2001); - US$ 495'000.-- nebst Zins zu 5 % seit 9. Januar 2002 (mittlerer Verfall 10. Juli 2001 - 9. Juli 2002); - US$ 544'500.-- nebst Zins zu 5 % seit 9. Januar 2003 (mittlerer Verfall 10. Juli 2002 - 9. Juli 2003); - US$ 598'950.-- nebst Zins zu 5 % seit 9. Januar 2004 (mittlerer Verfall 10. Juli 2003 - 9. Juli 2004). 2. Von den Beträgen gemäss Ziffer 1 hievor ist der durch Urkunden nachgewiesene bzw. der mit zumutbaren Anstrengungen erzielbare Ersatzverdienst der Klägerin zwischen 10. Juli 2000 und 9. Juli 2004 im entsprechenden Jahr abzuziehen. 3. Das Klagebegehren vom 25. Juli 2000 wird über den Betrag von US$ 23'940.-- zufolge Gegenstandslosigkeit abgeschrieben. 4. Die Widerklage wird abgewiesen. 5. Der Klägerin wird Frist gesetzt bis 30. September 2011 zum Einreichen der Urkunden über ihren im Zeitraum zwischen 10. Juli 2000 und 9. Juli 2004 erzielten Ersatzverdienst. 6. Der Antrag der Beklagten, es sei ein Gutachten über die Lohnentwicklung zu erstellen, wird abgewiesen." B.b. Dagegen erhob die Beschwerdegegnerin Berufung an das Obergericht des Kantons Solothurn und beantragte: "1. Die Berufung sei gutzuheissen und die Dispositiv-Ziffern 1., 2., und 4. des Urteils vom 30. August 2011 des Richteramts Olten-Gösgen (...) seien aufzuheben und die Angelegenheit sei an die Vorinstanz zur neuen Entscheidung in der Sache zurückzuweisen. Eventualiter: 2. Die Berufung sei gutzuheissen und die Dispositiv-Ziffern 1., 2., und 4. des Urteils vom 30. August 2011 des Richteramts Olten-Gösgen (...) seien aufzuheben, und die Klage sei vollumfänglich abzuweisen und es sei festzustellen, dass die Klägerin gegenüber der Beklagten über keine Ansprüche verfügt. 3. (...)." Die Beschwerdeführerin erhob Anschlussberufung und beantragte: "Die Berufung sei vollumfänglich abzuweisen, unter Kosten- und Entschädigungsfolgen (zzgl. MWST) zulasten der Beklagten. Es sei die Beklagte in Abänderung von Dispositiv-Ziffer 1 des erstinstanzlichen Entscheides zu verpflichten, der Klägerin insgesamt USD 2'889'298.-- (Gesamtschaden vor Anrechnung von Ersatzverdienst) nebst Zins zu 5 % seit 1. Juli 2000 zu bezahlen, (...)." Mit Urteil vom 8. Januar 2013 hiess das Obergericht des Kantons Solothurn die Berufung gut, soweit es darauf eintrat, hob die Dispositiv-Ziffern 1 und 2 des Urteils des Amtsgerichts Olten-Gösgen vom 30. August 2011 auf und wies die Klage ab. Ebenso wies es die Anschlussberufung ab. Die Gerichtskosten auferlegte es zu neun Zehnteln der Beschwerdeführerin und verpflichtete diese, der Beschwerdegegnerin eine (reduzierte) Parteientschädigung von Fr. 48'000.-- auszurichten (Dispositiv-Ziffern 4 und 5). Anders als das Amtsgericht verneinte das Obergericht, dass mit dem Schreiben vom 24. März 2000 zwischen den Parteien ein Arbeitsvertrag zustande gekommen sei. C. Gegen diesen Entscheid des Obergerichts des Kantons Solothurn erhebt die Beschwerdeführerin Beschwerde in Zivilsachen mit folgenden Rechtsbegehren: "1. Der angefochtene Entscheid sei aufzuheben und es sei die Beklagte entsprechend dem erstinstanzlichen Urteil zu verpflichten, der Klägerin folgende Beträge zu bezahlen: - USD 4'698.-- nebst Zins zu 5 % seit 1. Juli 2000; - USD 50'000.-- nebst Zins zu 5 % seit 10. Juli 2000; - USD 450'000.-- nebst Zins zu 5 % seit 9. Januar 2001 (mittlerer Verfall 10. Juli 2000 bis 9. Juli 2001); - USD 495'000.-- nebst Zins zu 5 % seit 9. Januar 2002 (mittlerer Verfall 10. Juli 2001 bis 9. Juli 2002); - USD 544'500.-- nebst Zins zu 5 % seit 9. Januar 2003 (mittlerer Verfall 10. Juli 2002 bis 9. Juli 2003); - USD 598'950.-- nebst Zins zu 5 % seit 9. Januar 2004 (mittlerer Verfall 10. Juli 2003 bis 9. Juli 2004); wobei von den vorstehenden Beträgen wiederum entsprechend dem erstinstanzlichen Urteil der durch Urkunden nachgewiesene bzw. der mit zumutbaren Anstrengungen erzielbare Ersatzverdienst der Klägerin zwischen 10. Juli 2000 und 9. Juli 2004 im entsprechenden Jahr abzuziehen sei. 2. Die Beklagte sei ferner entsprechend der klägerischen Anschlussberufung zu verpflichten, der Klägerin den Betrag von USD 696'150.-- entsprechend 50 % des Bonus sowie von USD 50'000.-- als Entschädigung im Sinne von Art. 337c Abs. 3 OR, alles nebst Zins zu 5 % seit 1. Juli 2000, zu bezahlen. 3. Das Verfahren sei zur Festlegung des nachgewiesenen bzw. des mit zumutbaren Anstrengungen erzielbaren Ersatzverdienstes der Klägerin zwischen dem 10. Juli 2000 und 9. Juli 2004 an das Amtsgericht Olten-Gösgen zurückzuweisen; alles unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten. Eventualantrag: Der angefochtene Entscheid sei aufzuheben und das Verfahren sei zu neuer Entscheidung im Sinne der bundesgerichtlichen Erwägungen an die Vorinstanz zurückzuweisen; unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten. Subeventualantrag: Ziffern 4 und 5 des angefochtenen Entscheides seien aufzuheben und es seien die Gerichtskosten des Berufungsverfahrens den Parteien je zur Hälfte aufzuerlegen und es seien die Parteientschädigungen für das Berufungsverfahren gegenseitig wettzuschlagen; unter Kosten- und Entschädigungsfolgen zu Lasten der Beklagten." Die Beschwerdegegnerin beantragt, auf die Beschwerde sei nicht einzutreten, eventuell sei sie abzuweisen. Die Vorinstanz schliesst unter Hinweis auf die Erwägungen im angefochtenen Urteil auf Abweisung der Beschwerde. Die Parteien reichten unaufgefordert Replik und Duplik ein. D. Mit Präsidialverfügung vom 16. April 2013 wurde das Gesuch der Beschwerdegegnerin um Sicherstellung einer allfälligen Parteientschädigung abgewiesen. Mit Präsidialverfügung vom 3. Juni 2013 wurde das Gesuch der Beschwerdeführerin, der Beschwerde die aufschiebende Wirkung zu erteilen, abgewiesen.