With formula fields, date artithemetic is done in days.

Example: MyDateField__c - 5 substracts 5 days.

To substract a conceptual month you could do MyDateField__c - 30 to subtract 30 days.

However, not every month is exactly 30 days, so if you need very accurate result you will need to consider either:

(a) complicated formula, or

(b) rely on apex to do the date calculation for you, such as in a trigger or have process builder call an invocable apex class whenever the record or field value changes.

Formula Functions

For reference, please see these documentation articles about date/time functions in formula fields:

• Using Date and Date/Time Values in Formulas
• Formula Operations and Functions A-H
• Sample Date Formulas

Apex Methods

• Date Methods

Your first formula was probably the closest. Here's the revised version.

The IsPickVal function requires two parameters, separated by a comma. The IsChanged function requires one parameter, the field to check for changes.

OR(
  AND( ISPICKVAL([Opportunity].StageName, "Prospecting"),
       ISBLANK([Opportunity].NextStep) ),
  AND (ISPICKVAL([Opportunity].StageName, "Prospecting"),
   ISCHANGED([Opportunity].StageName),
  NOT(ISBLANK([Opportunity].NextStep)),
  NOT(ISCHANGED([Opportunity].NextStep)) ) )