How can I do a matplotlib scatter plot with a categorical x-axis, that allows me to specify the marker and color based on a third variable?

Since you only specify your x-values and not your y-values, it is difficult to know your exact goal. But you can use the following code to create a scatter plot with categorical data. I chose to plot the 'Order' column as y-values, but you can also modify the code to plot something else or reorder you data as you like. So here you go:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

data = {'Order': np.arange(4), 'Movie Title': ['a', 'b', 'c', 'd'], 'Genre': ['genre2', 'genre1', 'genre1','genre2']}

df = pd.DataFrame.from_dict(data)

fig, ax = plt.subplots()
ax.scatter(df['Movie Title'], df['Order'],
           c=['blue' if g=='genre1' else 'red' for g in df['Genre']])
plt.show()