Is it possible to pick your Ed25519 public key? Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this as hard as solving one of SHA-512 or the discrete logarithm problem?
If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation.

Here's a diagram of how Ed25519 works, note how keys are generated:



(Image source.)

A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 - 11).

To recap the image and slides: The secret is hashed and public key is derived from the "left half" of the hash. The left half is manipulated to be value $a$, which is a bit string with a few conditions. Then $a$ is applied to a curve point $B$ to produce the public key $A$.

The critical thing to note is that the seed's hash output is used in key generation. Apparently implementations differ on what they store as the private key, but the algorithm itself does not need the original secret, only the hash from it. This means that if you control the implementation you use, you can just make up any hash that suits your purposes and you don't need to care what the corresponding secret would be. (This prevents the need to finding any sort of SHA-512 pre-image.) We can use this by working backwards from the desired public key value and deciding what hash value we want.

The goal of this attack is to choose the value of $A$, or to at least choose something very similar to it. Call the new target public key we're trying to build $A'$, then if $A'$ is a valid public key there is an $a'$ such that $a'B = A'$. This reduces to finding the inverse on the elliptic curve, $a' = AB^{-1}$, which is actually the Discrete Logarithm problem and certainly non-trivial to calculate. But if you could find a valid $a'$, you would have everything you need.

As an important side-note, not all values of $a$ are valid in the scheme. See the Ed25519 paper for all restrictions for $a$ (I believe they are all listed on pg 6). There aren't very many restrictions, I think the most restrictive one is that $a$ be divisible by 8 (ie, the low three bits are 0). Assuming you can can calculate the $a'$ from a chosen $A'$, you could just pick random $A'$s until you find one that produces a valid $a'$. This step would prevent you from explicitly choosing your public key, because you have no guarantee that the desired value for $A'$ is valid. You can probably find a valid $A'$ after only a few tries, so just flip a bit here and there in the desired $A'$ and you should be able to find one that works and has a small Hamming distance from the original desired $A'$, which is probably good enough to produce keys that look alike.

If you have $a'$ then you have the public key and you can create a corresponding private key. You can make up a random "right-side" of the SHA-512 hash value and incorporate the new $a'$ to construct the private key.

This all assumes you can control the implementation and solve the necessary discrete logarithm. Regarding the implementation, the NaCl project has a high-speed performance-oriented implementation of Ed25519, and as such it stores as much pre-computed data as possible in the private key. It would allow you to perform this sort of manual crafting of the keys. But in general, with other implementations, you may have no such luck. I would think that for most attacks, the attacker should be assumed to be able to choose the implementation they use.

(Hopefully this is all correct, I hadn't looked at Ed25519 before this.)