Pre-1933 Prussian history
The name "Prussia" originally referred to a region consisting of the present-day Kaliningrad Oblast of Russia, northeastern Poland (approximately Warmia-Masuria) and southwestern Lithuania. It was inhabited by (Old) Prussians, who spoke a language similar to Lithuanian and Latvian.
German settlement of the region began with the Prussian Crusade of 1230, in which the Teutonic Knights helped Poland Christianize Prussia at swordpoint. The Knights declared their own state, which would ultimately fight and lose wars against Poland, and get split into the Duchy of Prussia and Royal Prussia.
Recall that until 1871, "Germany" was not a nation-state as we know it today. It was a patchwork of dozens of small kingdoms, principalities, duchies, and city-states, loosely united in the Holy Roman Empire.
One of these German states was Brandenburg, which in 1594 had Prince-elector John Sigismund marry a Prussian duchess. In 1618, their realms were united into Brandenburg-Prussia, which became a kingdom in 1701.
Over the next 170 years, long story short, Prussia fought some wars and expanded its territory, to approximately the area of the US state of New Mexico. To help manage its territory, Prussia divided itself into provinces. In roughly east-to-west order:
- East Prussia (Ostpreußen), capital Königsberg
- West Prussia (Westpreußen), capital Danzig
- Posen, capital Posen
- Silesia (Schlesien), capital Breslau, in 1919 divided into:
- Upper Silesia (Oberschlesien), capital Oppeln
- Lower Silesia (Niederschlesien), capital Breslau
- Pomerania (Pommern), capital Stettin
- Brandenburg, capital Potsdam
- Berlin was split off into its own city-province in 1881
- Saxony (Sachsen), capital Magdeburg
- Schleswig-Holstein, capital Kiel
- Hesse-Nassau (Hessen-Nassau), capital Kassel
- Hanover (Hannover), capital Hanover
- Hohenzollern, capital Sigmaringen, a small Prussian exclave within the present-day state of Baden-Württemberg
- Westphalia (Westfalen), capital Münster
- Rhine Province (Rheinprovinz), capital Koblenz

Prussia would invite its allies from the Austro-Prussian War (1866) and Franco-Prussian War (1870-71) to form the German Empire in 1871. This was a federal state (analogous to the USA), in which states could have their own laws, their own heads of state (mostly monarchs), and recognize their own citizenship. But it was a very lopsided federation, with Prussia having 64% of the Empire's land area, 60-62% of its population, and being home to the Kaiser.
After Germany lost WW1, the empire became a republic, and the Kingdom of Prussia became the Free State of Prussia. But Prussia's province system remained largely intact, except that the loss of Danzig and the Polish Corridor severely reduced the provinces of Posen and West Prussia. The awkward leftover small pieces of these provinces were combined into a new province of Posen-West Prussia, except for the Marienwerder region east of the Corridor which was incorporated into East Prussia.

For most of the Weimar era, Prussia's politics were dominated by the leftist Social Democratic Party and Prime Minister Otto Braun. Braun's coalition lost its majority in 1932, but the parliament failed to agree on a successor. With the Prussian government crippled and failing to deal with ongoing unrest, the federal government, then headed by President Paul von Hindenburg and Chancellor Franz von Papen, issued an emergency degree putting Prussia under direct administration by the national government, with Papen as Reichskommissar. This was the end of Prussian self-government.
Under Hitler's regime
The First Gleichschaltung Law on March 31, 1933 dissolved all state legislatures except for Prussia's (which was already under control of the central government), making Germany into a unitary state. While the states still existed on paper, they now had no power, and were effectively replaced by the Nazi gau system.

East Prussia was one of these gaue, and it was expanded to include the Memel Territory from Lithuania and some occupied Polish territory. But it was no longer an exclave, with West Prussia (Reichsgau Danzig-Westpreußen) and Posen (Reichsgau Wartheland) having been reincorporated into the Reich.
After WW2
Otto Braun approached the Allies to reinstate the pre-1932 democratic Prussian government. But the allies had other ideas: Giving a large chunk of Prussian territory to Poland and Russia, and dividing what was left of northern Germany into British and Soviet occupation zones. Prussia did not fit into this new map of Germany, and was formally abolished by the Allied Control Council on February 25, 1947.
Direct answers to your question
What exactly was East Prussia between 1933 and 1945? Was it part of a larger government, and which one?
It was a gau (province) of the Third Reich. The Prussian state effectively did not exist at the time.
Until 1933, Prussia and East Prussia were both provinces of the Weimar Republic.
Not quite. East Prussia was a province of Prussia, which was a federal state of the Weimar Republic.
Beginning in 1933, they were provinces in the German Reich.
"Prussia" was de facto not an administrative division of the Third Reich. Its territory was split between about 20 gaue.
During the end of the war, the Red Army occupied East Prussia. It later became part of Russia, and Königsberg is now Kaliningrad.
Yes, except that not all of East Prussia became part of Russia, just the central region around Königsberg/Kaliningrad. The southern part became part of Poland, and the northern Memel Territory became part of Lithuania (then also part of the USSR, but separate from the Russian SFSR).
Prussia remained part of Germany after their surrender, and remains so today.
The state of Prussia was formally abolished in 1947 (though it had already ceased to operate as an autonomous state in 1932). The western portion of the former Prussia remained in Germany, divided between multiple new states. However, about half of Prussia's pre-WW1 territory, and all of its pre-1618 territory, including East Prussia, is now part of Poland, Russia, or Lithuania.