Summary
Crucibles are lined with refractory materials. Steel processing makes use of graphite or a combination of chromite and magnesite for direct contact with the melt. Cast iron processing often uses engineered clays, also known as alumina-magnesia-silica mixtures. Graphite is harder to form than clay-type refractories. To be suitable as a refractory, a material must meet a number of property requirements to be both economical and safe.
Refractory Materials
As you noted, iron has a high-end melting point of about 1,540 °C on the far left side of the $\textrm{Fe-C}$ phase diagram below, in the form of pure iron. There are two categories of materials with higher melting points, but only a few of those materials are both economical and safe. Generally, any material with a melting point high enough to withstand the melting points of commercially used metals such as iron, copper, and aluminum are called refractory materials.

Source: ispatguru.com
Refractory Metals (Not Useful for Foundries)
The first category of high melting point materials, of which you noted one material, are called refractory metals. Note that these are not generally referred to as refractories or refractory materials in the foundry industry. They consist of niobium, molybdenum, tungsten, tantalum, and rhenium, (Nb, Mo, W, Ta, Re) and have melting points ranging from about 2,500 °C to 3,500 °C. While the melting points are high enough and they have sufficient strength as structural materials, and some impact toughness to boot, there are a number of factors limiting their use.
- High reactivity with oxygen
- High reactivity with other metals
- High cost per weight
- High density
- High heat capacity
- High heat conduction
- Difficult to shape (requires either carefully controlled melting in a vacuum or powder metallurgy)
Refractory Ceramics (Useful for Foundries)
The second category of refractory materials are based on a variety of ceramics, and are called refractory ceramics, or more commonly just refractories. However, not just any ceramic is suitable. Ideally the ceramic would have extremely high atomic bond strength, or higher affinity for oxygen than the metal being melted. These would make the material relatively inert with respect to the molten metal. Such a ceramic must also be easily formable, have low heat capacity and heat conduction, and should be reasonably inexpensive.
Graphite is a reasonable choice for direct contact with steel and aluminum as the carbon-carbon bond strength is very high and it has a sufficiently high melting temperature, higher than its decomposition temperature in atmosphere. Graphite is somewhat more expensive to form than alternatives, though the crucibles tend to last longer. Graphite crucibles are high strength, though as with all ceramics low impact toughness. It has low density and lower heat capacity and heat conductivity than the refractory metals. Magnesite $\left(\textrm{MgCO}_3\right)$ and chromite $\left(\textrm{FeCr}_2\textrm{O}_4\right)$ are also common steel refractories.
Other choices are those systems below the $\textrm{Fe} + \textrm{O}_2 \rightleftharpoons \textrm{FeO}_2$ line on the Ellingham diagram below.
Chromia $\left(\textrm{Cr}_2\textrm{O}_3\right)$ can be used for some materials, but has high density and high heat capacity, as well as somewhat higher cost.
Silica $\left(\textrm{SiO}_2\right)$ is suitable for metals and alloys with lower melting temperatures, but has low thermal shock resistance. Pure silica (fused silica) has much higher thermal shock resistance but is very expensive and difficult to form. It is used in telescope mirrors.
Alumina $\left(\textrm{Al}_2\textrm{O}3\right)$ and magnesia $\left(\textrm{MgO}\right)$ are commonly used in cast-iron applications, where graphite is preferred for low alloy steel. Engineered clays, which are effectively specific mixtures of alumina, magnesia, and silica, are also frequently used for large-scale cast iron applications as they are very inexpensive and very easy to form in-place in 100 ton and larger applications. Additionally, cast iron has a lower melting point than steel (see the vertical line at about 4.3% carbon on the $\textrm{Fe-C}$ phase diagram and follow it up to the liquid region) and thus somewhat less strict requirements on refractory durability and reactivity.
Generally, lime $\left(\textrm{CaO}\right)$ is not used for structural materials as it is too brittle and tends to turn to powder quickly. It is however sometimes used as a binder additive, but the industry is moving away from this as calcium attacks other refractories reducing durability. See the Ellingham diagram below: lime is lowest on the diagram.
Titania $\left(\textrm{TiO}2\right)$ and manganese oxide $\left(\textrm{MnO})\right)$ are not generally used, though I do not know why; likely some combination of heat capacity and mechanical properties.
Ellingham Diagram (Selecting Stable Refractories)
The way to read an Ellingham Diagram, for our purposes, is that moving up on the graph means a decreasing affinity for oxygen, while moving down means an increasing affinity. The diagonal lines with chemical equations indicate the standard free energy of that reaction (vertical axis) at the given temperature (horizontal axis). If, at a given temperature, one reaction line is above another, the higher reaction will proceed toward pure metal plus oxygen (chemical reduction) while the lower reaction will proceed toward metal oxide (chemical oxidation). Therefore, refractory materials with higher affinity for oxygen than the molten metal will be chemically stable during melting. Note that additional diagrams exist or can be made for non-oxide materials using thermodynamic principles and some experimentation, and are a harder to come by on the internet.

Source: Cambridge Ellingham Diagram Tutorial